506. Relative Ranks

xiaoxiao2021-02-28  9

题目描述:

Given scores of N athletes, 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".

思路一:

时间复杂度O(nlogn),空间复杂度O(n)。

class Solution { public String[] findRelativeRanks(int[] nums) { String[] res = new String[nums.length]; int[] tmp = Arrays.copyOf(nums, nums.length); Arrays.sort(tmp); HashMap<Integer, Integer> map = new HashMap<>(); for (int i = tmp.length - 1; i >= 0; i--) map.put(tmp[i], tmp.length - i); for (int i = 0; i < nums.length; i++) { if (map.get(nums[i]) == 1) res[i] = "Gold Medal"; else if (map.get(nums[i]) == 2) res[i] = "Silver Medal"; else if (map.get(nums[i]) == 3) res[i] = "Bronze Medal"; else res[i] = map.get(nums[i]) + ""; } return res; } } 思路二:

时间复杂度O(n),空间复杂度O(max-min)。

class Solution { public String[] findRelativeRanks(int[] nums) { String[] res = new String[nums.length]; int max = nums[0]; int min = nums[0]; for (int num : nums) { if (num > max) max = num; if (num < min) min = num; } int[] hashTable = new int[max - min + 1]; for (int i = 0; i < nums.length; i++) hashTable[nums[i] - min] = i + 1; int index = 1; for (int i = hashTable.length - 1; i >= 0; i--) { if (hashTable[i] != 0) { if (index == 1) res[hashTable[i] - 1] = "Gold Medal"; else if (index == 2) res[hashTable[i] - 1] = "Silver Medal"; else if (index == 3) res[hashTable[i] - 1] = "Bronze Medal"; else res[hashTable[i] - 1] = index + ""; index++; } } return res; } }思路三:

class Solution { public String[] findRelativeRanks(int[] nums) { String[] res = new String[nums.length]; TreeMap<Integer, Integer> map = new TreeMap<>(Collections.reverseOrder()); for (int i = 0; i < nums.length; i++) map.put(nums[i], i); int index = 1; for (Integer value : map.values()) { res[value] = String.valueOf(index); index++; } for (int i = 0; i < res.length; i++) { if (res[i].equals("1")) res[i] = "Gold Medal"; else if (res[i].equals("2")) res[i] = "Silver Medal"; else if (res[i].equals("3")) res[i] = "Bronze Medal"; } return res; } }

转载请注明原文地址: https://www.6miu.com/read-2250312.html

最新回复(0)