未分類

Third Maximum Number

Array, Go, LeetCode

Third Maximum Number

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

1
2
3
4
5
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.

Example 2:

1
2
3
4
5
6
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned 
instead.

Example 3:

1
2
3
4
5
6
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.
提示 解題應用
Array Array

Default:

1
2
3
func longestPalindrome(s string) int {
}

解答思路:

寫下來有兩個重點，一個是題目帶的參數會有32位元int的極小值，意味著初始化如果是0的情況下，比大小可能會產生問題，所以預設前三個大小的值一定也要是32位元int的極小值，另外一個重點是在判斷如果沒有第三大的數時要回傳最大的數，這邊可以用一hashmap來篩選共有多少不相同獨特的數字，最後如果hashmap的長度不滿3表示不可能有第三大的數，就可以直接回傳最大的數，至於前三大的數怎麼知道，就是將陣列一個個與前三個值相比，比較大就取代掉僅僅如此。

程式碼解說:

一開始先初始化前三大數的值為int的32位元極小值及一hashmap來知道有多少獨特的數字，接著便是開始利用迴圈遍歷整個陣列，如果該值存在在hashmap之中表示已經重覆出現在前三大數中，此時就不需要在做判斷，如果尚未出現過的話則與前三大數做比較，如果比最大的值還大則原本第二大取代第三大，原本第一大取代第二大，再來才將最大值的位置給該值存放，而其它比第二大的值或第三大的值還大則一樣依序將值往後推，最後只要判斷hashmap的長度如果沒有超過3，表示獨特的數不足3因此不存在第三大的數，回傳最大值，若有超過3則回傳第三大的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
first := math.MinInt32
second := math.MinInt32
third := math.MinInt32
hashMap := make(map[int]int)
for _, v := range nums {
	_, ok := hashMap[v]
	if !ok {
		if v >= first {
			third = second
			second = first
			first = v
		} else if v >= second {
			third = second
			second = v
		} else if v >= third {
			third = v
		}
		hashMap[v] = v
	}
}
if len(hashMap) < 3 {
	return first
}
return third

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func thirdMax(nums []int) int {
	first := math.MinInt32
	second := math.MinInt32
	third := math.MinInt32
	hashMap := make(map[int]int)
	for _, v := range nums {
		_, ok := hashMap[v]
		if !ok {
			if v >= first {
				third = second
				second = first
				first = v
			} else if v >= second {
				third = second
				second = v
			} else if v >= third {
				third = v
			}
			hashMap[v] = v
		}
	}
	if len(hashMap) < 3 {
		return first
	}
	return third
}

總結:

要找出一陣列中第三大的數有兩個重點，一個是題目帶的參數會有32位元int的極小值，意味著初始化如果是0的情況下，比大小可能會產生問題，所以預設前三個大小的值一定也要是32位元int的極小值，另外一個重點是在判斷如果沒有第三大的數時要回傳最大的數，這邊可以用一hashmap來篩選共有多少不相同獨特的數字，最後如果hashmap的長度不滿3表示不可能有第三大的數，就可以直接回傳最大的數，至於前三大的數怎麼知道，就是將陣列一個個與前三個值相比，比較大就取代掉僅僅如此。

分享到