面试题 17.10. 主要元素(C++)

GeekLiHua

发布于 2025-01-21 10:41:20

6200

代码可运行

文章被收录于专栏：JavaJava

运行总次数：0

代码可运行

面试题 17.10. 主要元素

数组中占比超过一半的元素称之为主要元素。给你一个整数数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

我的代码

C++

// 解析：这个题就是一个统计每个数字出现频率的简单题
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> mp;
        for (auto num:nums) // 统计每个数字的频率
        {
            mp[num] ++;
        }
        for(auto itm:mp) // 然后再遍历哈希表 然后寻找出现频率超过一半的数字
        {
            if (itm.second >= ((int)nums.size() + 1) / 2) return itm.first; // 这里有个小细节就是需要在除以2之前+1
        }
        return -1;
    }
};

Java

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        count = 0;
        int length = nums.length;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
        return count * 2 > length ? candidate : -1;
    }
}

C

int majorityElement(int* nums, int numsSize) {
    int candidate = -1;
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (count == 0) {
            candidate = nums[i];
        }
        if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    count = 0;
    int length = numsSize;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == candidate) {
            count++;
        }
    }
    return count * 2 > length ? candidate : -1;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-02-17，如有侵权请联系 cloudcommunity@tencent.com 删除

int