leetcode506.相对名次

题目描述跳转leetcode详情

给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都互不相同。
运动员将根据得分决定名次，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：
名次第 1 的运动员获金牌 “Gold Medal” 。
名次第 2 的运动员获银牌 “Silver Medal” 。
名次第 3 的运动员获铜牌 “Bronze Medal” 。
从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 “x”）。
使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/relative-ranks
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题之前先了解下堆的相关基础概念

什么是堆？

堆是一种基于完全二叉树实现的抽象数据结构，具有以下特点：

堆可以是最大堆（父节点的值大于等于其子节点的值），也可以是最小堆（父节点的值小于等于其子节点的值）。
堆中每个节点的值都满足堆的性质，即任何一个父节点都比其子节点大（或小）。
堆通常使用数组实现，其中任何一个节点的下标为i，则其父节点的下标为(i-1)/2，左子节点的下标为2i+1，右子节点的下标为2i+2。
堆支持插入和删除操作，插入操作会使堆重新满足堆的性质，删除操作通常是删除最大值或最小值的操作，在最大堆中，删除操作会删除堆顶元素（即最大值），并重新调整堆以满足堆的性质。

堆是一种非常重要的数据结构，常见的应用包括排序算法（如堆排序、优先队列等）和图算法（如最短路径算法、最小生成树算法等）的优化。

优先队列

PriorityQueue（优先队列）是一种基于优先级堆的队列数据结构，具有以下特点：

内部通过堆实现，堆的根节点是队列中最高或最低的元素（取决于使用的比较器或默认的自然排序）。
插入元素时，会根据它们的优先级自动进行排序。默认情况下，元素的顺序按照其自然顺序确定，也可以通过提供一个自定义的Comparator实现自定义排序。
可以进行快速的查找、删除最高/最低元素，并支持常用的队列操作，如插入、删除和查找操作。
PriorityQueue允许重复元素，但不保证它们存储的顺序。
PriorityQueue不是线程安全的，如果需要在多个线程中使用，需要进行同步处理。

解题

本来是想做每日一题1439.有序矩阵中的第 k 个最小数组和的，但是真的是毫无头绪，看了题解说是需要使用堆来完成（我真的不知道怎么去解决），决定由基础做起，边找到了简单的leetcode506.相对名次来开始学习堆的使用。

解题思路

创建HashMap来记录分数和下标之间的关系
创建一个最大堆，用于对给定的分数进行排序，从而确定每个开放者的名次。由于我们需要为每个运动员分配名次，所以我们还需要知道原始下标。在完成排序后，我们可以使用映射表来找到与给定分数对应的原下标，并将相应的奖牌或编号分配给该运动员。

class Solution {public String[] findRelativeRanks(int[] score) {String[] res = new String[score.length];// 1. 创建map来记录分数和下标的关系HashMap<Integer, Integer> map = new HashMap<>();// 向map里面加入值for(int i = 0; i< score.length; i++){map.put(score[i], i);}// 2. 创建最大堆，用来排序PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> b-a);// 添加数据for(int s : score){queue.offer(s);}// 遍历最大堆，取到int i = 0;while(!queue.isEmpty()){int curScore = queue.poll();// 取到该分数对应的下标int index = map.get(curScore);if(i == 0){res[index] = "Gold Medal";}else if(i == 1){res[index] = "Silver Medal";}else if(i == 2){res[index] = "Bronze Medal";}else{res[index] = String.valueOf(i+1);}i++;}return res;}}

使用最大堆解决！
在这里插入图片描述

ps:PriorityQueue<Integer> queue = new PriorityQueue<>();默认是从小到大的排序的，在括号中提供一个比较器可以覆盖默认行为，这里 (a, b) -> b - a 中的 lambda 表达式就表示用 b - a 的结果进行比较，以逆序排序。其值为正（例如 b > a）时，会返回 1，保证 b 放在 a 前；值为负时会返回 -1，保证 a 放在 b 前。