聖地亞歌

Leetcode P0229"Majority Element II" 题解

2020/11/07 Leetcode

博文中会简要介绍Leetcode P0229题目分析及解题思路。

“Majority Element II”是一道难度中等偏上的题目，官方给的空间复杂度为O(1)的解法这里不再阐述，本文只给出使用HashTable的最直接的思路。

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

这道题的思路是维护一个HashTable来计算每个不同元素出现的次数，对出现次数超过1/3的元素，我们将其加入数组并且维护当前数组内元素无重复。

以下是Java的题解代码实现。

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        Map<Integer, Integer> num2CountMap = new HashMap<>();
        
        List<Integer> majorities = new ArrayList<>();
        Set<Integer> majoritySet = new HashSet<>();
        int N = nums.length;
        for (int num: nums) {
            num2CountMap.put(num, num2CountMap.getOrDefault(num, 0)+1);
            if (num2CountMap.get(num) > N/3 && !majoritySet.contains(num)) {
                majorities.add(num);
                majoritySet.add(num);
            }
        }
        
        return majorities;
    }
}
Java

以下是C++的题解代码实现。

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        unordered_map<int, int> num2count;
        vector<int> majorities;
        
        int N = nums.size();
        for (int num: nums) {
            ++num2count[num];
            if (num2count[num] > N/3) {
                if (majorities.empty()) {
                    majorities.push_back(num);
                }
                else {
                    if (majorities[0] != num) {
                        majorities.push_back(num);
                        return majorities;
                    }
                }
            }
        }
        
        return majorities;
    }
};
C++

Search