LeetCode 169.Majority Element (求众数)

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

题目描述：

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

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

**示例 1:**

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

**示例 2:**

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

AC C++ Solution:

方案1：一目了然，不用多解释。

class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int n = nums.size();
            sort(nums.begin(),nums.end());
            
            int lo = n/2, hi = n/2; 
            while(nums[lo] == nums[n/2])
                lo --;
            
            while(nums[hi] == nums[n/2])
                hi ++;
            
            if(hi-lo > n/2)
                return nums[n/2];
            else
                return 0;
    
            
        }
    };

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

class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            unordered_map<int, int> counts; 
            int n = nums.size();
            for (int i = 0; i < n; i++)
                if (++counts[nums[i]] > n / 2)
                    return nums[i];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，124人围观）

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

相关阅读

相关 [leetcode]: 169. Majority Element

1.题目描述 Given an array of size n, find the majority element. The majority element is t

Love The Way You Lie/ 2022年06月16日 03:50/ 0 赞/ 115 阅读

相关 LeetCode169. Majority Element解答

天气冷了，有男朋友的抱男朋友，有女朋友的抱女朋友，而我就比较牛逼了我不冷 \先来看一下题目 > Given an array of size n, find the

比眉伴天荒/ 2022年06月07日 11:26/ 0 赞/ 105 阅读

相关 LeetCode169. 求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 `⌊ n/2 ⌋` 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。示例 1:

阳光穿透心脏的1/2处/ 2022年05月23日 02:15/ 0 赞/ 175 阅读

相关 LeetCode 169.Majority Element (求众数)

题目描述：给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 `⌊ n/2 ⌋` 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。

港控/mmm°/ 2022年05月10日 15:00/ 0 赞/ 125 阅读

相关【LeetCode】169. 求众数

题目链接：[https://leetcode-cn.com/problems/majority-element/description/][https_leetcode-cn.

末蓝、/ 2022年05月08日 06:52/ 0 赞/ 149 阅读

相关 leetcode169. 求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。示例 1: 输入

约定不等于承诺〃/ 2022年03月31日 13:28/ 0 赞/ 148 阅读

相关 LeetCode 169. 求众数

169. 求众数给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并

旧城等待，/ 2022年03月29日 09:29/ 0 赞/ 180 阅读

相关 leetcode:169. 求众数

题目: 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。示例

╰+哭是因爲堅強的太久メ/ 2022年03月09日 00:54/ 0 赞/ 149 阅读

相关 LeetCode169.求众数

转载链接：[https://blog.csdn.net/qq\_41231926/article/details/86479848][https_blog.csdn.net_q

不念不忘少年蓝@/ 2022年02月18日 18:16/ 0 赞/ 211 阅读

相关 LeetCode : 169. Majority Element 众数

试题 Given an array of size n, find the majority element. The majority element is the el

ゞ浴缸里的玫瑰/ 2021年06月24日 16:11/ 0 赞/ 328 阅读