Skip to content

2512. Reward Top K Students 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  vector<int> topStudents(vector<string>& positive_feedback,
                          vector<string>& negative_feedback,
                          vector<string>& report, vector<int>& student_id,
                          int k) {
    vector<int> ans;
    vector<pair<int, int>> scoreAndIds;
    unordered_set<string> pos{positive_feedback.begin(),
                              positive_feedback.end()};
    unordered_set<string> neg{negative_feedback.begin(),
                              negative_feedback.end()};

    for (int i = 0; i < report.size(); ++i) {
      int score = 0;
      istringstream iss(report[i]);
      for (string word; iss >> word;) {
        if (pos.count(word))
          score += 3;
        if (neg.count(word))
          score -= 1;
      }
      scoreAndIds.emplace_back(-score, student_id[i]);
    }

    partial_sort(scoreAndIds.begin(), scoreAndIds.begin() + k,
                 scoreAndIds.end());
    transform(
        scoreAndIds.begin(), scoreAndIds.begin() + k, back_inserter(ans),
        [](const pair<int, int>& scoreAndId) { return scoreAndId.second; });
    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback,
                                   String[] report, int[] student_id, int k) {
    List<Integer> ans = new ArrayList<>();
    Pair<Integer, Integer>[] scoreAndIds = new Pair[report.length];
    Set<String> pos = Arrays.stream(positive_feedback).collect(Collectors.toSet());
    Set<String> neg = Arrays.stream(negative_feedback).collect(Collectors.toSet());

    for (int i = 0; i < report.length; ++i) {
      int score = 0;
      for (final String word : report[i].split(" ")) {
        if (pos.contains(word))
          score += 3;
        if (neg.contains(word))
          score -= 1;
      }
      scoreAndIds[i] = new Pair<>(score, student_id[i]);
    }

    Arrays.sort(scoreAndIds,
                (a, b)
                    -> a.getKey().equals(b.getKey()) ? a.getValue() - b.getValue()
                                                     : b.getKey() - a.getKey());

    for (int i = 0; i < k; ++i)
      ans.add(scoreAndIds[i].getValue());
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:
    scoreAndIds = []
    pos = set(positive_feedback)
    neg = set(negative_feedback)

    for sid, r in zip(student_id, report):
      score = 0
      for word in r.split():
        if word in pos:
          score += 3
        if word in neg:
          score -= 1
      scoreAndIds.append((-score, sid))

    return [sid for _, sid in sorted(scoreAndIds)[:k]]