精华内容
下载资源
问答
  • leetcode 求众数

    2019-08-12 12:57:00
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 示例2: 输入: [2,2,1,1,1...

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

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

    示例 1:

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

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

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/majority-element

    算法一:两重循环枚举,最坏时间复杂度为$n^2$ (过不了

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int n=nums.size();
            int res=0;
            for(int i=0;i<n;++i){
                int num=nums[i];
                int ans=0;
                for(int j=0;j<n;++j){
                    if(num==nums[j])ans++;
                }
                if(ans>n/2){
                    res=num;
                    break;
                }
            }
            return res;
        }
    };

    算法二:哈希表存储个数,复杂度为n

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

    算法三:摩尔投票法(核心思想:遍历一遍记录众数,众数肯定不会被消解完,最后记录的肯定是众数,因为最坏情况也就是其他被误当为众数,而真正的众数会将count减为0,而找到真正的众数

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int num=nums[0];//众数,先假设它是众数
            int count=1;
            for(int i=1;i<nums.size();++i){
                if(count==0){
                    num=nums[i];
                    count=1;
                }
                else if(num==nums[i]){
                    count++;
                }
                else{
                    count--;
                }
            }
            return num;
        }
    };

    转载于:https://www.cnblogs.com/clear-love/p/11339076.html

    展开全文
  • LeetCode 求众数

    2019-10-08 10:37:28
    题目链接:https://leetcode-cn.com/problems/majority-element/ 题目大意:  略。 分析:  略. 代码如下: 1 class Solution { 2 public: 3 int majorityElement(vector<int>& nums) { ...

    题目链接:https://leetcode-cn.com/problems/majority-element/

    题目大意:

      略。

    分析:

       略.

    代码如下:

     1 class Solution {
     2 public:
     3     int majorityElement(vector<int>& nums) {
     4         int ans = nums[0];
     5         int cnt = 1;
     6         
     7         for(int i = 1; i < nums.size(); ++i) {
     8             if(ans == nums[i]) ++cnt;
     9             else { // 两个两个消,最后剩下来的就是众数
    10                 if(--cnt < 0) {
    11                     ans = nums[i];
    12                     cnt = 1;
    13                 }
    14             }
    15         }
    16         
    17         return ans;
    18     }
    19 };
    View Code

     

    转载于:https://www.cnblogs.com/zaq19970105/p/11475451.html

    展开全文
  • Leetcode 求众数

    2019-04-16 06:46:10
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例1: 输入: [3,2,3] 输出: 3 示例2: 输入: [2,2,1,1,1,...

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

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

    示例 1:

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

    示例 2:

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

     

    O(n2),先排序,再比较.

    int cmpfunc(const void * a, const void * b) {
        return *(int *)a - *(int *)b;
    }
    
    int majorityElement(int *nums, int numsSize) {
    
        int i;
        short count;
        int ret;
        qsort(nums,numsSize,sizeof(int),cmpfunc);
    
        count = 1;
        ret = nums[0];
    
        for(i = 1; i < numsSize; i++)
            if(ret == nums[i]) {
                count++;
            } else if(count > numsSize/2) {
                return ret;
            } else {
                count = 1;
                ret = nums[i];
            }
    
        return ret;
    }
    
    

     

    法2

    int cmpfunc(const void * a, const void * b) {
        return *(int *)a - *(int *)b;
    }
     
    int majorityElement(int *nums, int numsSize) {
     
        qsort(nums,numsSize,sizeof(int),cmpfunc);
        return nums[numsSize/2];
    }

     

    法3
    因为题意假设这个数一定存在,所以这个数出现的次数大于其他所有数的和。

    int majorityElement(int *nums, int numsSize) {
    
        int i;
        short count = 1;
        int ret=nums[0];
        
        for(i=1;i<numsSize;i++) 
            if(ret == nums[i]) {
                count++;
            } else {
                count--;
                if(count == 0) {
                    ret = nums[i];
                    count = 1;
                }
            }
            
        return ret;
    }
    

     

    展开全文
  • leetcode求众数

    2019-10-29 14:40:35
    def majority(nums): set1=set(nums) print(set1) for i in set1: print(i) print(nums.count(i)) print(nums) print("=======") print(majority("223432"))
    def majority(nums):
        set1=set(nums)
        print(set1)
        for i in set1:
            print(i)
            print(nums.count(i))
            print(nums)
            print("=======")
    
    print(majority("223432"))
    展开全文
  • LeetCode 求众数II

    2019-03-03 08:43:57
    给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O...此题与上一题 LeetCode 求众数 就是这题众数的定义是出现超过 ⌊ n/3 ⌋ 次的。并且要求空间复杂度为O(1),...
  • leetcode求众数c++

    2019-04-29 13:06:51
    求众数 给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1...
  • LeetCode 求众数 C语言

    2019-07-22 11:54:17
    方法二:LeetCode官方题解中的投票算法,感觉思路真的很棒,首先假设第一个数为众数记为suf,遍历数组,若与suf相等的数则count+1,若不相等则-1,当count==0时,将suf改为此时的元素值,这样去掉了相等数量的两个...
  • LeetCode 求众数 II

    2019-10-08 10:37:26
    题目链接:https://leetcode-cn.com/problems/majority-element-ii/ 题目大意:  略。 分析:  k个一起删, 最后check一下即可. 代码如下: 1 #define foreach(i,c) for (__typeof(c.begin()) i = c....
  • 169 leetcode 求众数

    2019-11-09 18:50:51
    题目描述: 根据题目描述,①最容易想到的,最暴力的方法就是算出来每一个数字出现的次数,然后再判断;②另一个时间复杂度为O(n)的方法是:可以想象一下开心消消乐,两个相同的颜色会被消除;...
  • LeetCode 求众数 C++

    2019-01-04 21:35:16
    利用关联容器map,&lt;key,value&gt;中令数组中的数字为key,数字出现的次数为...最后遍历map,将value值大于众数的数据输出 代码如下: class Solution { public: int majorityElement(vector&lt...
  • leetcode 求众数 II

    2019-02-06 23:27:17
    给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1)。 示例 1: 输入: [3,2,3] 输出: [3] 示例 2: ... majorityElement(...
  • LeetCode求众数C++版

    2019-05-26 22:12:14
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,...
  • 【Java】Leetcode求众数

    2019-09-03 11:11:55
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,...
  • LeetCode 求众数 (C++)

    2019-04-02 15:50:02
    给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2...
  • 给定一个大小为 n 的数组,找到其中的众数众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。 示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2...
  • LeetCode原题链接: https://leetcode-cn.com/problems/majority-element-ii/solution/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/ 摩尔投票法,解决的问题是如何在任意多的候选人中,选出票数超过一半...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 736
精华内容 294
关键字:

leetcode求众数