---
# System prepended metadata

title: 2512. Reward Top K Students
tags: [Leetcode, Sorting, Priority Queue, Medium]

---

# 2512. Reward Top K Students
###### tags: `Leetcode` `Medium` `Sorting` `Priority Queue`
Link: https://leetcode.com/problems/reward-top-k-students/description/
## 思路
```list.add()``` – takes O(1) time
```list.add(index, element)``` – on average runs in O(n) time
因此尽量不用第二个

按照题意来 先算出每个学生的point 然后排序即可
## Code
```java=
class Solution {
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        int n = student_id.length;
        Set<String> positive = new HashSet<>(Arrays.asList(positive_feedback));
        Set<String> negative = new HashSet<>(Arrays.asList(negative_feedback));
        int[][] points = new int[n][2];

        for(int i=0; i<report.length; i++){
            int point = 0;
            for(String s:report[i].split(" ")){
                if(positive.contains(s)) point += 3;
                else if(negative.contains(s)) point -=1;
            }
            points[i][0] = point;
            points[i][1] = student_id[i];
        }

        Arrays.sort(points, (a, b)->(b[0]!=a[0]?b[0]-a[0]:a[1]-b[1]));
        ArrayList<Integer> ans = new ArrayList<>();
        for(int i=0; i<k; i++){
            ans.add(points[i][1]);
        }
        return ans;
    }
}
```
```python=
class Solution:
    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:
        stud = []
        pos, neg = set(positive_feedback), set(negative_feedback)
        for rep, id in zip(report, student_id):
            point = 0
            for s in rep.split(" "):
                if s in pos: point += 3
                if s in neg: point -= 1
            stud.append((-point, id))
        
        stud.sort()
        return [sid for _, sid in stud[0:k]]
```