推 ILoveErr: 大師 05/08 11:56
→ Rushia: 存索引 Comparator用score[i]比較就不用pair 05/08 11:57
推 JIWP: 別卷了 05/08 11:59
→ sustainer123: Comparator可以這樣用?學到了 05/08 11:59
→ digua: 大師 05/08 12:15
→ DJYOSHITAKA: 剩我不懂家把了 05/08 13:16
※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/relative-ranks/description
: 506. Relative Ranks
: 給你一個不重複數字的整數陣列，score[i] 表示第 i 個人的分數，前三個分數高的人分
: 別是"Gold Medal","Silver Medal","Bronze Medal"，第四高的是 4，第五高的是 5，...
: 求出一個陣列 res， res[i] 表示第 i 個人是什麼獎項。
: 思路：
: 1.用 max_heap 依照分數排序，然後遍歷heap，如果是前三個就給他頒獎，不然他就是第
: i 名。
: py code:
: -------------------------------------
: class Solution:
: def findRelativeRanks(self, score: List[int]) -> List[str]:
: n = len(score)
: max_heap = []
: for i in range(n):
: heapq.heappush(max_heap, (-score[i], i))
: rank = 4
: top_three = ['Bronze Medal', 'Silver Medal', 'Gold Medal']
: res = [''] * n
: while max_heap:
: idx = heapq.heappop(max_heap)[1]
: if top_three:
: res[idx] = top_three.pop()
: else:
: res[idx] = str(rank)
: rank += 1
: return res
: -------------------------------------
Java Code:
import java.util.*;
class Solution {
class Pair {
int score;
int index;
public Pair(int score, int index) {
this.score = score;
this.index = index;
}
}
public String[] findRelativeRanks(int[] score) {
int n = score.length;
PriorityQueue<Pair> maxHeap = new PriorityQueue<>((a, b) -> b.score -
a.score);
for (int i = 0; i < n; i++) {
maxHeap.offer(new Pair(score[i], i));
}
Queue<String> top = new LinkedList<>();
top.offer("Gold Medal");
top.offer("Silver Medal");
top.offer("Bronze Medal");
String[] result = new String[n];
int rank = 4;
while (!maxHeap.isEmpty()) {
Pair p = maxHeap.poll();
if (!top.isEmpty()) {
result[p.index] = top.poll();
} else {
result[p.index] = String.valueOf(rank++);
}
}
return result;
}
}
Java真的好難寫喔 哇哇嗚嗚嗚
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.170.119 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715140552.A.A03.html