[LeetCode] 229. Majority Element II

轉自LeetCode

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.

<Solution>

Majority Element 的衍生題，這次不保證有解，且 array 有可能是空的

還有一個改變是，最低次數變成 floor(size / 3)

想法如下

• 因為最低次數變成 floor(size / 3)，所以至多會有 2 個 majority element

• 使用 Boyer-Moore Majority Vote Algorithm 來解這個問題

• 因為題目不保證有解，所以最後還是要檢查一下候選人的出現次數是否符合要求

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

	class Solution {
	public:
	vector<int> majorityElement(vector<int>& nums) {
	vector<int> ans;
	if(nums.empty()) {
	return ans;
	}
	//>> use Boyer-Moore Majority Vote algorithm
	int candidate_1 = 0, cnt_1 = 0;
	int candidate_2 = 0, cnt_2 = 0;
	for(const auto &n : nums) {
	if(n == candidate_1) {
	++cnt_1;
	}
	else if(n == candidate_2) {
	++cnt_2;
	}
	else if(cnt_1 == 0) {
	candidate_1 = n;
	cnt_1 = 1;
	}
	else if(cnt_2 == 0) {
	candidate_2 = n;
	cnt_2 = 1;
	}
	else {
	--cnt_1;
	--cnt_2;
	}
	}
	//>> make sure candidate_1 and candidate_2 are majority elements
	cnt_1 = cnt_2 = 0;
	for(const auto &n : nums) {
	if(n == candidate_1) {
	++cnt_1;
	}
	else if(n == candidate_2) {
	++cnt_2;
	}
	}
	//>> find the ans
	const int threshold = nums.size() / 3;
	if(cnt_1 > threshold) {
	ans.push_back(candidate_1);
	}
	if(cnt_2 > threshold) {
	ans.push_back(candidate_2);
	}
	return ans;
	}
	};

view raw majorElementInArray2_1.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun majorityElement(nums: IntArray): List<Int> {
	var candidate1 = 0
	var candidate2 = 0
	var count1 = 0
	var count2 = 0
	for(n in nums) {
	when {
	n == candidate1 -> ++count1
	n == candidate2 -> ++count2
	count1 == 0 -> {
	++count1
	candidate1 = n
	}
	count2 == 0 -> {
	++count2
	candidate2 = n
	}
	else -> {
	--count1
	--count2
	}
	}
	}
	// get the exact appear time
	count1 = 0
	count2 = 0
	for(n in nums) {
	if(n == candidate1) {
	++count1
	} else if (n == candidate2) {
	++count2
	}
	}
	val ans = arrayListOf<Int>()
	val threshold = nums.size / 3
	if(count1 > threshold) {
	ans.add(candidate1)
	}
	if(count2 > threshold) {
	ans.add(candidate2)
	}
	return ans
	}
	}

view raw majority_element_II.kt hosted with ❤ by GitHub