[LeetCode] 169. Majority Element

轉自LeetCode

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

<Solution>
這題是要找出重複次數超過 floor(size / 2) 的值

想法如下

• 用 hash map 記錄每個值的出現次數，如果超過 floor(size/2) 就回傳答案

• 時間複雜度O(n)，空間複雜度O(n)

code如下
c++

	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	const int threshold = nums.size() >> 1;
	unordered_map<int, int> map;
	for(const auto &n : nums) {
	++map[n];
	if(map[n] > threshold) {
	return n;
	}
	}
	return -1;
	}
	};

view raw majorElementInArray_1.cpp hosted with ❤ by GitHub

另一種解法是投票法，時間複雜度依然是 O(n)，空間複雜度可以變成 O(1)

想法如下

• 每個數都投票給自己，如果當前答案就是自己，那票數加 1；如果不是，票數減 1

• 當 cnt = 0 的時候，先假設答案就是當前的值，並 ++cnt

• 如果 cnt != 0，那當前的值相等於目前的答案，則 ++cnt；反之，則 --cnt

code如下(參考資料)
c++

	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	int ans = 0, cnt = 0;
	for(const auto &n : nums) {
	if(cnt == 0) {
	ans = n;
	++cnt;
	}
	else {
	(n == ans) ? ++cnt : --cnt;
	}
	}
	return ans;
	}
	};

view raw majorElementInArray_2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun majorityElement(nums: IntArray): Int {
	var count = 0
	var ans = 0
	for(n in nums) {
	when {
	count == 0 -> {
	++count
	ans = n
	}
	n == ans -> ++count
	else -> --count
	}
	}
	return ans
	}
	}

view raw majority_element.kt hosted with ❤ by GitHub

上面這個想法，還可以改寫成 bit operation 的方式

想法如下

• 每個位元去計算是 1 多，還是 0 多。如果是 1 多，則最後的答案在此位元就一定是 1；反之則是 0

• 時間複雜度是O(n)，空間複雜度是 O(1)

code如下(參考資料)
c++

	class Solution {
	public:
	int majorityElement(vector<int>& nums) {
	int ans = 0;
	for(int i = 0; i < 32; i++) {
	int zeros = 0, ones = 0;
	for(const auto &n : nums) {
	if((n & (1 << i)) != 0) {
	++ones;
	}
	else {
	++zeros;
	}
	}
	if(ones > zeros) {
	ans |= (1 << i);
	}
	}
	return ans;
	}
	};

view raw majorElementInArray_3.cpp hosted with ❤ by GitHub