未分類

Relative Ranks

Go, LeetCode

Relative Ranks

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”.

For Example:

1
2
3
4
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:

  1. N is a positive integer and won’t exceed 10,000.
  2. All the scores of athletes are guaranteed to be unique.

Default:

1
2
3
func findRelativeRanks(nums []int) []string {
}

解答思路:

原本的作法是一個個紀錄所有名次的分數，如果比該名次大就將所有該名次(包含)向後退一名，之後再將新分數放至該名次之中，但這種作法只有找前三名或較少名次適用，因為每次要將所有後頭名次向後退太耗時間，因此倒不如一開始就做排序之後在照順序來發獎牌，不過在那之前要先將每個分數的位置給儲存下來才開始做排序，最後再給前三名獎牌而其餘的人則是只有名次。

程式碼解說:

一開始就先以一迴圈將每個分數所對應的位置儲存至hashmap之中，其中key值為分數而value則是index值的位置，之後就將所有的分數做排序，這邊我們就直接用內建的library來做排序，因為排序完分數是從小至大，所以我們就從分數最大的開始發獎牌，因此由陣列後頭向前遍歷，隨著名次一一增加從第一名發到第三名都為獎牌(字串)，其餘的則是將名次轉為字串做儲存(不能直接強制轉，會變ASCII)，待獎牌與名次分配完之後就回傳結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
rank := 1
result := make([]string, len(nums))
scoreIndex := make(map[int]int)
for index, score := range nums {
	scoreIndex[score] = index
}
sort.Ints(nums)
for i := len(nums) - 1; i >= 0; i-- {
	switch rank {
	case 1:
		result[scoreIndex[nums[i]]] = "Gold Medal"
	case 2:
		result[scoreIndex[nums[i]]] = "Silver Medal"
	case 3:
		result[scoreIndex[nums[i]]] = "Bronze Medal"
	default:
		result[scoreIndex[nums[i]]] = strconv.Itoa(rank)
	}
	rank++
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func findRelativeRanks(nums []int) []string {
	rank := 1
	result := make([]string, len(nums))
	scoreIndex := make(map[int]int)
	for index, score := range nums {
		scoreIndex[score] = index
	}
	sort.Ints(nums)
	for i := len(nums) - 1; i >= 0; i-- {
		switch rank {
		case 1:
			result[scoreIndex[nums[i]]] = "Gold Medal"
		case 2:
			result[scoreIndex[nums[i]]] = "Silver Medal"
		case 3:
			result[scoreIndex[nums[i]]] = "Bronze Medal"
		default:
			result[scoreIndex[nums[i]]] = strconv.Itoa(rank)
		}
		rank++
	}
	return result
}

總結:

一陣列包含每位選手的分數(不重覆)，若只是要找前三名則可以一一比較並將較小的分數名次向後退，但若需列出整個陣列的名次，則先將所有分數做排序再照順序來發獎牌，而如果後者是要全部做排序，在開始之前需先記錄下每個分數儲存的位置，最後才以此位置來分配分數所對應的獎牌。

分享到