《剑指offer》 第39题 数组中出现次数超过一半的数字

思路1：数组排序后，如果符合条件的数存在，则一定是数组中间那个数。否则，需要进行判断，看数组中的数是否有一半和中间的数相等，相等则存在符合条件的数，不存在则直接返回0

import java.util.Arrays;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        int count=0;
        //记录数组中等于该数组中间索引的元素  
        for(int i=0;i<array.length;i++){
            if(array[i]==array[array.length/2]){
                count++;
            }
        }
        if(count>array.length/2){ //如果数量超过一半，则说明符合条件，否则返回0
            return array[array.length/2];
        }else{
            return 0;
        }

    }
}

思路2：不使用排序，(这个方法也叫摩尔投票法，有兴趣的可以去看看leetcode第169题，只是牛客上的题数组中可能出现没超过一半的数字)遍历数组过程中保存两个值：一个是数组中某一数字，另一个是次数。遍历到下一个数字时，若与保存数字相同，则次数加1，反之减1。若次数=0，则保存下一个数字，次数重新设置为1。由于要找的数字出现的次数比其他数字之和还多，那么要找的数字肯定是最后一次把次数设置为1的数字。（当一个数的出现次数比其他数出现次数的总和还多时，说明这个值是符合条件的）
友情提示：当一个数最终的time>0，并不意味着这个数就符合要求了，比如在数组{1,2,3,4,5,6,7,7,7,8,9,10,10}中，运行完for循环后，最终会记录数字10，并且time为2。这一操作只是尽可能的在找一个出现次数较多的数。因此还需要进行一轮判断if。在第二轮过程中，count才是计数，判断数组中的数是否等于这个找出来的数（因为在不满足的条件的情况下，找出来的这个数只是出现次数较多，而非最多），如果有一半以上等于这个数，就找到，否则，不存在。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //非法输入判断
        if(array == null || array.length <= 0)
            return 0;
        int times = 1;
        int number = array[0];
        //查看是否存在有可能次数大于数组长度一半的数字
        for(int i = 1; i < array.length; i++) {
            if(times <= 0) {
                number = array[i];
                times = 0;
            }
            if(array[i] == number) {
                times++;
            }
            else { 
                times--;
            }
        }
        //判断该数字次数是否大于数组长度一半
        if(times > 0) {
            int count = 0;
            for(int i = 0; i < array.length; i++) {
                if(array[i] == number)
                    count++;
            }
            if(count > array.length / 2)
                return number;
            else
                return 0;
        }
        else
            return 0;
    }
}

思路3：
中位数，又称中点数，中值。中位数是按顺序排列的一组数据中居于中间位置的数，即在这组数据中，有一半的数据比他大，有一半的数据比他小
如果这个数组的满足条件，那么他的出现次数超过一般的数字一定是中位数。所以找到数组的中位数，就找到了结果。而想找到一个数组的中位数，并且不通过排序的话。联想到快排中有一个核心方法即Partition函数

Partition函数的功能是可以在数组中任取一个数字，将数组中比该数字小的均放置在该数字左边，比该数字大的均放在该数字右边。最后返回该数字的下标small，并赋给index。此时，index的左边都比index小，右边都比index大（左边只保证小，并没有排序）
利用这个函数的特性：
1.设数组长度一半为middle。数组起点为start，终点为end。
2.若index大于middle，说明中位数在start到index之间。更新end = index - 1；
若index小于middle，说明中位数在index到end之间。更新start = index + 1；
若index等于middle，说明array[index]即为中位数。
3.判断取得的中位数是否满足次数大于长度一半。（这样的操作最终结果是获得了整个数组的中位数）
思路3不好的地方在于，更改了输入的数据，改变了输入的数组元素的位置，并且通过Pratition找到的是中位数，中位数不一定是结果！{1，2，3，4，5，6，7，7，8}的中位数是5

import java.util.Random;
public class Solution { 
    public int MoreThanHalfNum_Solution(int[] array) {
        int start = 0, end = array.length - 1;
        int index = Partition(array, start, end);
        int middle = array.length / 2;
        while(index != middle) {
            if(index > middle) {
                end = index - 1;
                index = Partition(array, start, end);
            }   
            else {
                start = index + 1;
                index = Partition(array, start, end);
            }

        }
        int times = 0;
        for(int i = 0; i < array.length; i++) {
            if(array[i] == array[index]) 
                times++;
        }
        if(times > array.length / 2)
            return array[index];
        else
            return 0;
    }
    public int Partition(int[] array, int start, int end) {
        Random rand = new Random(); 
        int index = rand.nextInt(end - start + 1) + start;
      //这里使用随机数是优化，若选取的不合理，会导致时间复杂度增加
        Swap(array, index, end);
        int small = start - 1;
        for(index = start; index < end; index++) {
            if(array[index] < array[end]) {
                small++;
                if(small != index) 
                    Swap(array, small, index);
            }
        }
        small++;
        Swap(array, small, end);
        return small;
    }
    public void Swap(int[] array, int a, int b) {
        int tmp;
        tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
}

总结：思路1是排序，排完序后整个数组都很直观。思路2是尽量找出现次数较多的数，如果出现次数超过一半，一定可以出来，而找出来的数不能保证是出现次数最多。思路3是不通过排序，找数组的中位数，然而破坏了原数组的顺序。