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

Offer_39

题目描述

方法一：使用map存储数字出现的次数

public class Offer_39 {

    public int majorityElement(int[] nums) {

        Map<Integer,Integer> map = new HashMap<>();

        int len = nums.length;

        int ans = -1;

        for(int num : nums){

            int cnt = 0;

            if(map.containsKey(num)){

                cnt = map.get(num);

            }

            map.put(num, ++cnt);

            if(cnt > len / 2){

                ans = num;

                break;

            }

        }

        return ans;

    }

}

注：该方法的时间和空间复杂度均为 O(N)。

方法二：先将数字排序，然后取中位数

/**

 * 使用先排序再取中位数的方法。时间复杂度为 O(logn)

 */

class Offer_39_2 {

    public int majorityElement(int[] nums) {

        Arrays.sort(nums);

        return nums[nums.length / 2];

    }

}

摩尔投票法

/**

 * 使用摩尔投票法：票数正负抵消的原理。此方法时间和空间复杂度分别为 O(N)和 O(1)，为本题的最佳解法。

 */

class Offer_39_1 {

    public int majorityElement(int[] nums) {

        int result = 0, votes = 0;

        for(int num : nums){

            if(votes == 0)

                result = num;

            votes += (num == result) ? 1 : -1;

        }

        return result;

    }

}

剑指 Offer 39. 数组中出现次数超过一半的数字 + 摩尔投票法的相关教程结束。