剑指Offer 29 数组中出现次数超过一半的数字

题目描述

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

思路

快排，快排的思想就是分区，放置一个哨兵，左边比他小，右边比他大；
他自然就是中位数了，而出现超过一半的数，在排序的时候一定有一个会出现在中间；（2，3，2）–>（2，2，3）大概就这个意思；
快排的想法除了分区以外就是递归的想法；一个哨兵，找出一大一小两个区，那么接着往下分解，最后到无法再分解时，就有序了；
而我们并不需要有序，我们只想得到中位数，左边小，右边大；所以我们只需要找到这么一个哨兵恰好在中间，而且分好区；这样他肯定就是中位数了；
智力的思考
简单地说，这种方法正常人恐怕想不到；

如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。

在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。

代码

public class Nine {
    public  static  void  main(String [] arg)
    {
        int a[] = {1,2,3,2,2,2,5,4,2};
        int b[]=new int[1];
        System.out.println(MoreThanHalfNum_Solution1(a));
    }
  static   public int MoreThanHalfNum_Solution(int [] array) {
        int a=0;
        if (array==null||array.length<=0)
            return a;
        else if (array.length==1)
            return 1;
        int start = 0;
        int end = array.length-1;
        int middle = array.length>>1;
        int index = AdujustArray(array,start,end);
        while (index!=middle)
        {
            if (index>middle) {
                end = index-1;
                index = AdujustArray(array, start, end);
            }
            else {
                start=index+1;
                index = AdujustArray(array, start, end);
            }
        }
        int number = array[middle];
        int times = 0 ;
        for (int i = 0; i < array.length; i++) {
            if (array[i]==number)
                times++;
        }
        if (times*2<=array.length)
        return a;
        else
            return number;
    }
    public  static  int AdujustArray(int array[], int left , int right)
    {
        int i =left;
        int j= right;
        int x = array[left];
        while (i<j)
        {
            while (array[j]>=x&&i<j)
                j--;
            if (i<j) {
                array[i] = array[j];
                i++;
            }
            while (array[i]<x&&i<j)
                i++;
            if (i<j) {
                array[j] = array[i];
                j--;
            }
        }
        array[i]=x;
        return i;
    }
    public static  int MoreThanHalfNum_Solution1(int array[])
    {
        int a =0;
        if (array==null||array.length<=0)
            return a;
        else if (array.length==1)
            return array[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 (array[i]==result)
                {
                    times++;
                }
            else
                times--;
        }
        int number = result;
        int time = 0 ;
        for (int i = 0; i < array.length; i++) {
            if (array[i]==number)
                time++;
        }
        if (time*2<=array.length)
            return a;
        else
            return number;
    }
}

收获

最近几天都没有编程，好多事情唉。。。

2017-03-29