找出数组中超过一半以及三分之一的数

发表于 | 分类于

找出数组中超过一半的数（假设存在）
可以使用摩尔投票算法，也就是每次去抵消不同数字。也就是去对拼消耗，最坏情况就是自己的这一半消耗剩余的，好的情况就是他们自己也会去消耗。

例如：

输入：{1,2,1,3,1,1,2,1,5}

序号也表明了数组的下标
0.从第一个数字1开始，我们想要把它和一个不是1的数字一起从数组里抵消掉，但是目前我们只扫描了一个1，所以暂时无法抵消它，把它加入到array，array变成了{1}，result由于没有抵消任何元素所以还是原数组{1,2,1,3,1,1,2,1,5}。
1.然后继续扫描第二个数，是2，我们可以把它和一个不是2的数字抵消掉了，因为我们之前扫描到一个1，所以array变成了{},result变成了{1,3,1,1,2,1,5}
2.继续扫描第三个数1，无法抵消，于是array变成了{1},result还是{1,3,1,1,2,1,5}
3.接下来扫描到3,可以将3和array数组里面的1抵消,于是array变成了{},result变成了{1,1,2,1,5}
4.接下来扫描到1，此时array为空，所以无法抵消这个1，array变成了{1},result还是{1,1,2,1,5}
5.接下来扫描到1，此时虽然array不为空，但是array里也是1，所以还是无法抵消，把它也加入这个array,于是array变成了{1,1}
6.接下来扫描到2，把它和一个1抵消掉，至于抵消哪一个1，无所谓，array变成了{1},result是{1,1,5}
7.接下来扫描到1，不能抵消，array变成了{1,1}，result{1,1,5}
8.接下来扫描到5，可以将5和一个1抵消，array变成了{1},result变成了{1}至此扫描完成了数组里的所有数，result里剩了1，所以1就是大于一半的数组。

其实array中只有一种数，因为只有array为空或当前扫描到的数和array里的数字相同时才把这个数字放入array

所以代码实现起来，只需要一个变量来代表array中存放的数就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 public int Solution(int [] array) {
	if(array.length == 0) return 0;
	int num = 0;//保存次数(例如第7步中，有两个1，则次数为2）
	int myarray = array[0];//保存数字
	for(int i = 0; i < array.length; i++) {
		//如果次数为0，保存数字，次数置为1
		if(num == 0) {
			myarray = array[i];
			num = 1;
		}
		//次数不为1，当前数字与保存的数字相同时，次数加1
		else if (array[i] == myarray) {
			num++;
		}
		//当前数字与保存的数字不同时，次数减1
		else if (array[i] != myarray) {
			num--;
		}
	}
	return myarray;
}

那么如何找出出现次数大于三分之一的数呢？
思路一样，但是需要保存两个数去抵消

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
 public int Solution(int [] array) {
	if(array.length == 0) return 0;
	int num1 = 0;
	int num2 = 0;
	int res1 = array[0];
	int res2 = array[1];
	for(int i = 0; i < array.length; i++) {
	   
		if(num1 == 0 || array[i] == res1) {
			res1 = array[i];
			num1 += 1;
		}
	   
		else if (num2 == 0 || array[i] == res2) {
			res2 = array[i];
			num2 += 1;
		}
	   
		else{	
			num1--;
			num2--;
		}
	}
	//最终确定剩下的两个数是否大于三分之一
	return myarray;
}
Jie wechat
学就完事