欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

面试题39:数组中出现次数超过一半的数字

程序员文章站 2024-02-27 15:50:15
...
/**
 * Created by clearbug on 2018/2/26.
 *
 * 面试题39:数组中出现次数超过一半的数字
 */
public class Solution {

    public static void main(String[] args) throws InterruptedException {
        Solution s = new Solution();

        int[] arr = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(s.moreThanHalf1(arr));
        System.out.println(s.moreThanHalf2(arr));
    }

    /**
     * 首先说一下最简单却有不那么容易让人想到的方法:数组中有一个数字出现的次数超过数组长度的一半,也就是说它出现的次数比其他所有数字出现
     * 的次数的和还要多。
     *
     * 时间复杂度:O(n)
     *
     * @param arr
     * @return
     */
    public int moreThanHalf1(int[] arr) {
        int res = arr[0];
        int times = 1;
        for (int i = 1; i < arr.length; i++) {
            if (times == 0) {
                res = arr[i];
                times = 1;
            } else if (arr[i] == res){
                times++;
            } else {
                times--;
            }
        }
        return res;
    }

    /**
     * 第二种方法就是借助快速排序的思想:当数组大致有序时,出现次数超过一半的数字必然是位于数组的中间位置
     *
     * 时间复杂度:O(n)
     *
     * @param arr
     * @return
     */
    public int moreThanHalf2(int[] arr) {
        int middle = arr.length >> 1;
        int start = 0;
        int end = arr.length - 1;
        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 arr[middle];
    }

    private int partition(int[] arr, int start, int end) {
        int privot = arr[start];
        while (start < end) {
            while (arr[end] >= privot && end > start) {
                end--;
            }
            arr[start] = arr[end];
            while (arr[start] <= privot && end > start) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = privot;
        return start;
    }
}