// Boyer-Moore Vote Algorithm
// 从 nums[n] 数组里找到一个出现次数多于 n/2 次数的数
// 投票算法，抵消的思想

#include <stdio.h>

int majorityElement(int* nums) {
	int candidate = 0;
	int count = 0;
	const int n = sizeof(nums) / sizeof(int);
	
	candidate = nums[0];
	for (int i = 0; i < n; ++i) {
		if (candidate == nums[i]) count += 1;  // 找到相同的加1
		else count -= 1;  // 找不到就抵消一个计数
		if (count == 0) candidate = nums[i];  // 抵消换下一个数
	}
	return candidate;
}

int main(int argc, const char* argv[]) {
	int nums[] = {1,2,3,2,2,4,2,5,2,6,2}; // n = 10, 2有6个 可以知道必定至少有两个相同的数在一起
	fprintf(stdout, "%d\n", majorityElement(nums));
	return 0;
}