数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
方案一：
简单来想，就像游戏一样，5V5打平局，5V4就人数多的获胜，每个人都有属于自己的队伍，如果某支队伍超过了总人数一半就会获胜(这就是最后的检查环节)。也就是如果有2支队伍，一共9个人，遇到A队伍就++， 遇到B队伍就--，那么最后一个剩下的人，属于哪个队，哪个队的人数就多。本题也一样，最后一个剩下的数，很可能代表它的总数超过了一半，但是需要检查，等会讲为什么检查。
假设只有2支队伍，一共9个人，每组2个人pk，我们一一询问他们是哪个队伍的，以第一个人为例array[0]，array[0]和array[1]pk，如果是同一支队伍就++count，表示队伍多了1个人，如果不相等就抵消，最后剩下的的那个人属于哪只队伍就获胜，比如
5，4，4，5，4，5，4，5，4
（54）（45）（45）（45）（4）
那么4超过了总数的一半。或者有很多队伍，有一只队伍超过的人数的一半，其余的混合队伍组合
比如5，1，5，2，5，3，5，4，5
（51）（52）（53）（54）（5）
那么5超过了队伍的一半
再来谈谈为什么需要检查？
1，2，3，4，5，6，7，8，9
（12）（34）（56）（78）（9），但是9出现次数并没有超过数组长度的一半，所以需要检查多的那个数是否超过数组长度的一半。
又比如
5， 1， 5， 2， 4， 3， 6， 7， 5
（51）（52）（43）（76）（5）最后留下了5，但是5出现次数并没有超过数组长度的一半，不符合。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if (array == null || array.length == 0) return 0;
if (array.length == 1) return array[0];
int len = array.length;
int count = 1;
int res = array[0];
for (int i = 1; i < len; ++i) {
if (count == 0) {
res = array[i];
count = 1;
} else if (res == array[i]) {
++count;
} else {
--count;
}
}
return check(array, res) ? res : 0;
}
private boolean check(int[] arr, int res) {
int len = arr.length;
int count = 0;
for (int i = 0; i < len; ++i) {
if (arr[i] == res) {
++count;
}
}
return (count << 1) > len ? true : false;
}
}方法二：基于快排思想
如果一个排过序的数组，那么超过数组一半长度的数字，一定位于中间，反之不一定，需要检查，这个数字也就是统计学上的中位数。比如[1, 2, 2]， [1, 3, 3, 3]超过长度一半的一定位于中间，又比如[1, 2, 3]位于中间的不一定超过长度一半。
先在数组中随机选一个数字，然后调整数组中数字顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边，这也是快排思想。
如果我们选中的数字是数组的中位数，下标正好是n/2，那么在排序的过程中，如果下标小于n/2，那么中位数位于它的右边，如果下标大于n/2，那么中位数位于它的左边，过程用递归实现。直至下标正好是中位数，那么左边的数字比它小，右边的数字比它大，虽然还没有完全有序，但是已经足够了。继续左右递归这个过程是可以变成完全有序的，可以继续排序，但没必要。此时中间的数字出现次数一定超过了数组长度的一半（当然需要检查，原因同方案一）。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if (array == null || array.length == 0) return 0;
if (array.length == 1) return array[0];
int mid = array.length >> 1;
int start = 0;
int end = array.length - 1;
int index = partition(array, start, end);
while (index != mid) {
if (index < mid) {
start = index + 1; // 有序的中位数在右边区间
} else {
end = index - 1;
}
index = partition(array, start, end);
}
return check(array, index) ? array[index] : 0;
}
private boolean check(int[] arr, int index) {
int len = arr.length;
int count = 0;
for (int i = 0; i < len; ++i) {
if (arr[i] == arr[index]) {
++count;
}
}
return (count << 1) > len ? true : false;
}
private int partition(int[] arr, int start, int end) {
int i = start, j = end + 1;
int compareNum = arr[start];
while (true) {
while (arr[++i] < compareNum) {
if (i >= end) break;
}
while (compareNum < arr[--j]) {
if (j <= start) break;
}
if (i >= j) break;
swapNum(arr, i, j);
}
swapNum(arr, start, j);
return j;
}
private void swapNum(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}这种方法会改变原来的数组顺序，如果可以更改数组顺序，那么这一种方案是可行的。
方案一和方案二时间复杂度都是O（n）