LeetCode 169.Majority Element (求众数)

港控/mmm° 2022-05-10 15:00 264阅读 0赞

题目描述:

给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在众数。

示例 1:

  1. 输入: [3,2,3]
  2. 输出: 3

示例 2:

  1. 输入: [2,2,1,1,1,2,2]
  2. 输出: 2

AC C++ Solution:

方案1:一目了然,不用多解释。

  1. class Solution {
  2. public:
  3. int majorityElement(vector<int>& nums) {
  4. int n = nums.size();
  5. sort(nums.begin(),nums.end());
  6. int lo = n/2, hi = n/2;
  7. while(nums[lo] == nums[n/2])
  8. lo --;
  9. while(nums[hi] == nums[n/2])
  10. hi ++;
  11. if(hi-lo > n/2)
  12. return nums[n/2];
  13. else
  14. return 0;
  15. }
  16. };

方案2:用一个关联容器,key是nums[i]值,value是count计数值

  1. class Solution {
  2. public:
  3. int majorityElement(vector<int>& nums) {
  4. unordered_map<int, int> counts;
  5. int n = nums.size();
  6. for (int i = 0; i < n; i++)
  7. if (++counts[nums[i]] > n / 2)
  8. return nums[i];
  9. }
  10. };

发表评论

表情:
评论列表 (有 0 条评论,264人围观)

还没有评论,来说两句吧...

相关阅读