题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路

方法一：

首先将数组进行排序（快速排序），如果存在一个数字出现的次数超过数组长度的一半，那么此时第n/2个数字即为所求数字。
时间复杂度是：O(nlogn)

方法二：修改了输入的数组

由方法一可知，要求的数字就是排序好的数组的第n/2个数字。
所以，可以利用快速排序中的partition算法找下标是n/2的数字（此时n/2处的数字必然大于其左半部分的数字，并且小于其右半部分的数字）。比快速排布快，因为此方法只对半个部分进行partition。

面试题29 ：数组中出现次数超过一半的数字
这种情况的平均时间复杂度大致为：T(n) = n+n/2+n/4+n/8+….+1，很明显当n很大时，T(n)趋近于2n，也就是说平均情况下时间复杂度为O(n),但是这种情况下，最坏的时间复杂度依然为O(n*n)，最坏情况下（和快速排序的最坏情况类似，最大不平衡时），index总是位于数组的最左或最右边，这样时间复杂度为T(n) = n+n-1+n-2+n-3+….+1 = n(n-1)/2，显然，时间复杂度为O(n*n)，空间复杂度为O(1)。
最好情况下时间复杂度是（一次partition就正好在中间位置）：O（n）

方法三：不修改数组

面试题29 ：数组中出现次数超过一半的数字

代码实现

方法二：

import java.util.Random;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("array is invalid");
        }
//利用partiton算法找已排序数组的中位数
int length = array.length;
int middle = length >> 1;
int start = 0;
int end = length - 1;
int index = partition(array, start, end);
while (index != middle) {
if (index < middle) {
                start = index + 1;
                index = partition(array, start, end);
            } else {
                end = index - 1;
                index = partition(array, start, end);
            }
        }

int result = array[middle];
if (!checkMoreThanHalf(array, result)) {
            result = 0;
        }

return result;
    }

/**
 * 随机选取算法
 * @param data
 * @param start
 * @param end
 * @return
 */
public static int partition(int[] data, int start, int end) {
if (data == null || data.length <= 0 || start < 0 || end < 0 || data.length <= start || data.length <= end) {
throw new IllegalArgumentException("Invalid parameters in partition method!");
        }
int index = new Random().nextInt(end - start + 1) + start;
        swap(data, index, end);

int small = start - 1; //指向最后一个小于data[end]的元素
for (index = start; index < end; index++) {
if (data[index] < data[end]) {
                small++; //data[index]待放入的位置
if (small != index) {
                    swap(data, small, index);
                }
            }
        }
        small++; //放置data[end]
        swap(data, small, end);

return small;
    }

/**
 * 交换数组中两个元素
 * @param data
 * @param p
 * @param q
 */
public static void swap(int[] data, int p, int q) {
if (data == null || data.length <= 0 || p < 0 || q < 0 || data.length <= p || data.length <= q) {
throw new IllegalArgumentException("Invalid parameters in swap method!");
        }
int tmp = data[p];
        data[p] = data[q];
        data[q] = tmp;
    }

private boolean checkMoreThanHalf(int[] data, int result) {
int times = 0;
int length = data.length;
for (int i = 0; i < length; i++) {
if (data[i] == result) {
                times++;
            }
        }
if (times * 2 <= length) {
return false;
        }
return true;
    }
}

方法三：

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
if (array == null || array.length <= 0) {
 return 0;
        }
        int times = 1;
        int result = array[0];
for (int i = 1; i < array.length; i++) {
if (times == 0) {
result = array[i];
times = 1;
            } else if (result == array[i]) {
times++;
            } else {
times--;
            }
        }
if (times == 0) {
 return 0;
        }
if (!checkMoreThanHalf(array, result)) {
result = 0;
        }

 return result;

    }

    private boolean checkMoreThanHalf(int[] data, int result) {
        int times = 0;
        int length = data.length;
for (int i = 0; i < length; i++) {
if (data[i] == result) {
times++;
            }
        }
if (times * 2 <= length) {
 return false;
        }
 return true;
    }
}

秒客网