LeetCode 169.Majority Element (求众数)

港控/mmm° 2022-05-10 15:00 267阅读 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());
  7.         int lo = n/2, hi = n/2; 
  8.         while(nums[lo] == nums[n/2])
  9.             lo --;
  11.         while(nums[hi] == nums[n/2])
  12.             hi ++;
  14.         if(hi-lo > n/2)
  15.             return nums[n/2];
  16.         else
  17.             return 0;
  20.     }
  21. };

方案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 条评论，267人围观）

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

相关阅读