leetcode 中查找多数元素

Question

我的代码针对大多数输入运行，但对于输入：

nums = [6,6,6,7,7]

我得到：

7 // Output, but expected 6

谁能告诉我不正确的部分和正确的建议？

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int count = 1;
        HashMap<Integer, Integer> map = new HashMap<>();
        int i = 0;

        if (nums.length == 1) {
            return nums[0];
        } else {
            while (i < nums.length - 1) {
                if (nums[i] == nums[i + 1]) {
                    count++;
                    map.put(nums[i], count);
                    i++;
                } else {
                    i++;
                }

            }
        }

        int maxValueInMap = (Collections.max(map.values())); // This will return max value in the HashMap
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) { // Iterate through HashMap
            if (entry.getValue() == maxValueInMap) {
                return entry.getKey(); // Print the key with max value
            }
        }
        return -1;
    }
}

Answer 1

您只会递增

count

，而在遇到与前一个值不同的新值时绝不会重置它。

Answer 2

有两个同名问题“多数元素”和“多数元素 II”。第二个很有趣。我假设你也在问同样的问题。它基于Boyer-Moore 多数投票算法。下面给出的是两者的 C++ 解决方案。

多数元素

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int maj, count=0;
        for (int num:nums) {
            if (num==maj) { count++; continue; }
            if (count) { count--; }
            else { maj=num, count=1; } }
        return maj; } };

多数元素II

class Solution {
public:
    vector<int> majorityElement(vector<int> &nums, size_t m=3) {
    unordered_map<int, int> map;
    unordered_set<int> zeros;
    for (size_t i=0; i+1<m; ++i) {
        map[numeric_limits<int>::max()-i]=0;
        zeros.insert(numeric_limits<int>::max()-i); }
    for (int num: nums) {
        if (map.count(num)) {
            map[num]++;
            zeros.erase(num);
            continue; }
        if (zeros.size()) {
            map.erase(*zeros.begin());
            zeros.erase(zeros.begin());
            map[num]=1;
            continue; }
        for (auto &pair: map) {
            pair.second--;
            if (pair.second==0) { zeros.insert(pair.first); } } }
    for (auto &pair: map) { pair.second=0; }
    for (int num: nums) { if (map.count(num)) { map[num]++; } }
    vector<int> soln;
    int threshold=nums.size()/m;
    for (auto &pair: map) { if (pair.second>threshold) { soln.push_back(pair.first); } }
    return soln; } };

我希望这有帮助。 o7