剑指offer面试题系列

题目：数组中有一个数字出现的次数超过了数组长度的一半，请找出这个数字。

分析

首先要明白一个统计学规律：一个排序数组中出现次数超过一般的数字必然位于此数组的中间处。

此题有两种实现方法：

自己只想出来方法一：

思路： 由快速排序的分割思想得到启发，因为快排的每次分割数组都是将枢纽元放在正确的位置上，于是就想如果这个枢纽元正好位于此数组的中心就好了。但是并不是每次分割运气都这么好，于是可以使用递归的方式，当这个枢纽元的位置在数组中心的前面，则分割后面的部分，反之则分割前面的部分，如果位于中央，则直接返回此数字即可。

这样的算法复杂度：O(NlgN)级别。

看了剑指offer之后，发现有复杂度更小的精妙算法。根据这个思路写出了代码中的Solution2。

思路：可以声明一个变量 time，如果数组的下一个元素与前面的一个元素不一致，则减一，如果一致则加一。如果数组中有出现超过一半的数字，则此数字必然就是最后使 time 的值变为 0 的那个。妙哉！！！！！

这样的算法复杂度仅仅为：O(n).

代码实现

package com.study;

import java.util.Random;

/** 求数组中出现次数超过总次数一半的数字 */
public class suanfa16 {
    // solution 1
    /*
     * 最好在查出满足条件的元素时，检查一下数组是否符合题意，即 存在出现次数超过一半的数字
     */
    public static int FindNumberOverHalf(int[] arr, int start, int end) {
        int index = new Random().nextInt(end - start) + start;
        System.out.println("Index is : " + index);
        int pivot = arr[index];
        SwapNum(arr, index, end);

        int PartionNum = 0;
        int i = start - 1;
        int j = end;
        for (;;) {
            while (arr[++i] < pivot && i < end)
                ;
            while (arr[--j] > pivot && j > start)
                ;
            if (i >= j)
                break;
            else
                SwapNum(arr, i, j);
        }

        SwapNum(arr, i, end);

        PartionNum = i;
        if (PartionNum < arr.length / 2)
            PartionNum = FindNumberOverHalf(arr, PartionNum, end);
        if (PartionNum > arr.length / 2)
            PartionNum = FindNumberOverHalf(arr, start, PartionNum);

        return PartionNum;
    }

    public static void SwapNum(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // solution 2
    public static int FindPartionNum(int[] arr) {
        int time = 1;
        int preNum = arr[0];
        int result = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != preNum) {
                time--;
            } else {
                time++;
            }
            if (time == 0)
                result = arr[i];
            preNum = arr[i];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = { 1, 7, 2, 8, 7, 7, 7, 4, 7 };
        int[] arr = { 1, 7, 2, 4, 4, 4, 5, 4, 4, 2, 2, 2, 2, 2, 2, 2 };
        int index = FindPartionNum(arr);
        System.out.println("Index is : " + index
                + ", The number you want to find is : " + arr[index]);
    }
}

备注

如果需要考虑不规范数组，即数组中没有这样的数字存在的情况，还需要加一部分代码，以实现检查数组规范的情况。

总结

快排思想的再次运用。快速排序真是一个特别牛逼的排序啊，其思想不止在排序方面牛逼闪闪啊，还可以用到好多地方。

递归，这是一把神器。做了剑指offer的题也一半多了，总是会用到它。试着慢慢理解它吧！