2017-07-02 12:35:58 +0000   |     algorithm leetcode array   |   Viewed times   |    

题目

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in space.

主要思路

遇到这种majority的问题,可以考虑一下Boyer-Moore Majority Vote Algorithm,以及它的推广。

常规做法用HashMap记录频率。计算复杂度:,空间复杂度

虽然不符合in linear time and in $$O(1)$$ space的要求,但还是做一下。

代码

/**
 * 使用额外Map记录出现数字的频率
 * 计算复杂度:O(n),空间复杂度O(n)
 */
public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (Integer num : nums) {
            Integer freq = map.get(num);
            freq = (freq == null)? 1 : freq+1;
            map.put(num,freq);
        }
        List<Integer> result = new ArrayList<>();
        Integer target = nums.length / 3;
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            Integer freq = entry.getValue();
            if (freq > target) {
                result.add(entry.getKey());
            }
        }
        return result;
    }
}

结果

majority-element-two-1

Boyer-Moore Majority Vote Algorithm

看到这种找majority的题,就可以考虑这个Boyer-Moore Majority Vote Algorithm。这里要求出现频率 freq > ⌊ n/3 ⌋,不是 50%。所以需要做一个变化。

最终,出现次数 freq > ⌊ n/3 ⌋ 的数字,最多只有2个。所以就假设有一个大小为2的袋子。这个袋子叫2 reduced bag。先把里面只能装2个数,以及他们的频率统计。他们被初始化为nums[0]。然后遍历数组,

这里,重要的一个结论是:

经过上面这个过程,出现次数 freq > ⌊ n/3 ⌋ 的数字,必定都在这个袋子中。但袋子中的数字不一定都保证freq > ⌊ n/3 ⌋

所以最后还需要再遍历一遍数组,只统计袋子中2个数的频率,如果满足freq > ⌊ n/3 ⌋就确定为结果。

这个定理可以推广到任意K个数

如此维护的K Reduced Bag,出现次数 freq > ⌊ n/(K+1) ⌋ 的数字,必定都在这个大小为K的袋子中。但袋子中的数字不一定都保证freq > ⌊ n/(K+1) ⌋

代码

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums.length == 0) { return result; }
        int num1 = nums[0], num2 = nums[0], count1 = 0, count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (num == num1) {
                count1++;
            } else if (num == num2) {
                count2++;
            } else if (count1 == 0) {
                num1 = num; count1 = 1;
            } else if (count2 == 0) {
                num2 = num; count2 = 1;
            } else {
                count1--; count2--;
            }
        }
        count1 = 0; count2 = 0;
        for (int num : nums) {
            if (num == num1) { count1++; continue; }
            if (num == num2) { count2++; }
        }
        int target = nums.length / 3;
        if (count1 > target) { result.add(num1); }
        if (count2 > target) { result.add(num2); }
        return result;
    }
}

结果

majority-element-two-2