未分類

Majority Element II

Array, Go, LeetCode

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

提示 解題應用
Array Array/Slice

Default:

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

解答思路:

之前雖然有一篇Majority Element，不過當時是直接採用hashmap的方式來統計結果，但如果要只用O(1)的空間複雜度的話，基本上就是用互相抵消的方式來處理，也就是說先取第一個元素為基準(此時計數器初始為1)，如果碰到相同的元素就將計數器+1，碰到不同的就將計數器-1，當計數器歸0便以下一個元素為基準重新計算，遍歷完之後其基準值就會是結果(因為最多的元素超過一半，透過抵消的方式最後一定只剩下該元素)，上述的方式同樣也可以利用在這題要找出超過1/3總數的基準值(時間複雜度O(n)及空間複雜度O(1))，可想而之能超過1/3的基準值頂多只會有兩個，所以這次就只要設兩個基準值、兩個計數器來找出最多的兩個元素即可，不過最後還要再針對這個兩元素重新遍歷一次數列，並各別計算兩個的數量，因為雖然是最多的兩個元素，但也有可能其中一個特別多而導致另一個總數未超過1/3。

程式碼解說:

如思路所述，設定兩個基準值、兩個計數器來找出最多的兩個元素，不過並不需要為兩個基準值做初始化，因為兩個計數器一開始都為0，之後遍歷時會發現計數器為0而將取出的元素作為其對應的新基準值，接下來就是遍歷整個數列，如果碰到與基準值相同的元素就將對應的計數器+1，碰到都不同的就將兩個計數器-1，當有計數器歸0便以下一個元素為其對應的新基準值重新計算，這邊要注意取出任一基準值的元素時，不要將另一個基準值的計數器-1，否則會導致最多的兩個元素互相抵消而被取代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var count1 int
var count2 int
var candidate1 int
var candidate2 int
var major []int
for _, v := range nums {
	if v == candidate1 {
		count1++
	} else if v == candidate2 {
		count2++
	} else if count1 == 0 {
		candidate1 = v
		count1++
	} else if count2 == 0 {
		candidate2 = v
		count2++
	} else {
		count1--
		count2--
	}
}

遍歷完之後兩個的基準值就會是最多的兩個元素，還要再針對這個兩元素重新遍歷一次數列，並各別計算兩個的數量(在那之前要記得先重置兩個計數器為0)，最後再判斷兩個元素各別的數量是否超過總數的1/3，如果有才將其放入結果陣列之中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
count1 = 0
count2 = 0
for _, v := range nums {
	if v == candidate1 {
		count1++
	} else if v == candidate2 {
		count2++
	}
}
if count1 > len(nums)/3 {
	major = append(major, candidate1)
}
if count2 > len(nums)/3 {
	major = append(major, candidate2)
}
return major

完整程式碼:

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
27
28
29
30
31
32
33
34
35
36
37
38
39
func majorityElement(nums []int) []int {
	var count1 int
	var count2 int
	var candidate1 int
	var candidate2 int
	var major []int
	for _, v := range nums {
		if v == candidate1 {
			count1++
		} else if v == candidate2 {
			count2++
		} else if count1 == 0 {
			candidate1 = v
			count1++
		} else if count2 == 0 {
			candidate2 = v
			count2++
		} else {
			count1--
			count2--
		}
	}
	count1 = 0
	count2 = 0
	for _, v := range nums {
		if v == candidate1 {
			count1++
		} else if v == candidate2 {
			count2++
		}
	}
	if count1 > len(nums)/3 {
		major = append(major, candidate1)
	}
	if count2 > len(nums)/3 {
		major = append(major, candidate2)
	}
	return major
}

總結:

要從一數列中找出超過1/3總數的元素，且其時間複雜度為O(n)及空間複雜度為O(1)，可想而之能超過1/3總數的元素最多只會有兩個，而基本上就是用互相抵消的方式來處理，設定兩個基準值、兩個計數器來找出最多的兩個元素，如果碰到與基準值相同的元素就將對應的計數器+1，碰到都不同的就將兩個計數器-1，當有計數器歸0便以下一個元素為其對應的新基準值重新計算，遍歷完之後兩個的基準值就會是最多的兩個元素，不過最後還要再針對這個兩元素重新遍歷一次數列，並各別計算兩個的數量，因為有可能其中一個特別多而導致另一個總數未超過1/3。

分享到