leetcode506. Relative Ranks
leetcode506. Relative Ranks
题目要求
Given scores ofNathletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".
Example 1:
Input: [5, 4, 3, 2, 1] Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"] Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". For the left two athletes, you just need to output their relative ranks according to their scores.
Note:
- N is a positive integer and won't exceed 10,000.
- All the scores of athletes are guaranteed to be unique.
现有N名运动员的成绩，用一个正整数数组来表示，已知该正整数数组中的成绩均唯一。要求用一个String数组返回对应下标上运动员的相对排名，其中前三名分别标记为"Gold Medal", "Silver Medal"和"Bronze Medal"，其它则用数字表示排名。
思路和代码
这题直观的来看可以用排序得出运动员从高到低的得分，但是这样就丢失了分数原来的下标。因此，假如我们可以将0-n这n个数字进行排序，排序的标准为对应的运动员的成绩。再根据下标将排序结果依次写会。
过程如下：
假如一组运动员成绩为[1,3,2,5,4]
对应的下标为[0,1,2,3,4]
则对第二个数组按照其对应的成绩由低到高的排序结果为[3,4,1,2,0]
再根据这个结果依次将结果写入String数组中，
result[3]="Gold Medal", result[4]="Silver Medal", result[1]="Bronze Medal" result[2]="4" result[0]="5"代码如下：
public String[] findRelativeRanks(int[] nums) {
if (nums.length == 0) return new String[0];
Integer[] indexes = Stream.iterate(0, i -> i+1).limit(nums.length).sorted(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return nums[o2] - nums[o1];
}
}).toArray(Integer[]::new);
String[] result = new String[nums.length];
for (int i = 0 ; i<indexes.length ; i++) {
if (i == 0) {
result[indexes[i]] = "Gold Medal";
} else if (i == 1) {
result[indexes[i]] = "Silver Medal";
} else if (i == 2) {
result[indexes[i]] = "Bronze Medal";
} else {
result[indexes[i]] = String.valueOf(i+1);
}
}
return result;
}这里使用了JAVA内置的排序，也可以使用桶排序来降低时间复杂度。
public String[] findRelativeRanks(int[] nums) {
if (nums.length == 0) return new String[0];
int maxValue = IntStream.of(nums).max().getAsInt();
int[] buckets = new int[maxValue+1];
for (int i = 0 ; i<nums.length ; i++) {
buckets[nums[i]] = i+1;
}
int place = 1;
String[] result = new String[nums.length];
for (int i = buckets.length-1 ; i>=0 ; i--) {
if (buckets[i] == 0) continue;
if (place <= 3) {
if (place == 1) {
result[buckets[i]-1] = "Gold Medal";
} else if (place == 2) {
result[buckets[i]-1] = "Silver Medal";
} else {
result[buckets[i]-1] = "Bronze Medal";
}
} else {
result[buckets[i]-1] = String.valueOf(place);
}
place++;
}
return result;
}