[剑指Offer] 三种方法求解找出数组中出现次数超过一半的数字

• 题目描述：给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
  例如，输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

1）利用map

• 依次把数组中的元素插入到map中，元素的值为key，元素的个数为value，然后使其value与数组的一半大小做对比，若大于，则该元素就是我们要找的数字。

void test1_1(){
	vector<int> v1 = {1, 2, 3, 2, 2, 2, 5, 4, 2 };
	int half = v1.size() / 2;
	
	unordered_map<int, int> map;
	for (auto& e : v1){
		map[e]++;
		if (map[e] > half){
			printf("%d\n", e);
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2）利用库函数sort

• 使用库函数sort对数组元素进行排序，出现次数超过一半的数字一定会出现在排序后的中间位置上。
  注意：sort（）函数的头文件为< algorithm >

void test1_2(){
	vector<int> v1 = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
	int half = v1.size() / 2;
	sort(v1.begin(), v1.end());
	printf("%d\n", v1[half]);
}
1
2
3
4
5
6

3) 采取不同的数字进行抵消的思想

• 采取不同的数字进行抵消的思想，若下一个数与当前数相等，count++，否则count- -，当count为0时，重新设置当前数为我们的结果数字。

void test1_3(){
	vector<int> v1 = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
	int count = 0;
	int ret = 0;
	for (auto& e : v1){
		if (count == 0){
			ret = e;
			count++;
		}
		else{
			if (ret == e)
				count++;
			else
				count--;
		}
	}
	printf("%d\n", ret);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18