【算法】数组中出现次数超过一半的数字（Java）

题目

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

思路

数组中有一个数字出现的次数超过了数组长度的一半，如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过长度一半的数字，也就是说，这个数字实际上就是中位数，其实也就是得到数组中的第K大的数的变形。

代码

partition函数

public static int partition(int[] arr, int start, int end) {
    
        int point = arr[end];
        int i = start;
        int j = end;
        while (i < j) {
            while(i < j && arr[i] <= point) ++i;
            while(i < j && arr[j] >= point) --j;
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i];
        arr[i] = arr[end];
        arr[end] = temp;
        return i;
    }

解法

public static int find(int[] arr, int start, int end) {
        if (start < end) {
            int middle = (end + 1)/2;
            int index = partition(arr, start, end);
            while (index != middle) {
                if(index > middle){
                    end = index -1;
                    index = partition(arr, start, end);
                } else {
                    start = index +1;
                    index = partition(arr, start, end);
                }
            }
            return middle;
        }
        return -1;
    }

测试

public static void main(String[] args) {
        int[] arr= new int[]{1,2,3,2,2,2,5,4,2};
        int index = find(arr, 0, arr.length - 1);
        System.out.print(index);
    }