选择绝对众数

墨蓝 2022-07-12 05:08 156阅读 0赞

**绝对众数**的概念表示序列中的唯一众数，且出现的次数大于N2，N表示序列的长度。  
实际上在序列中如果某个数的出现次数超过该序列长度的一半，那么该数一定是唯一的众数。

解决这个问题的办法有多：  
1.排序，时间复杂度为O(nlogn)，返回nums\[N/2\]。  
2.使用hash，时间复杂度可以降低到O(n)，但需要额外的空间复杂度。

有更好的办法，O(n)的时间复杂度O(1)的空间复杂度。

从人的角度来看待这个问题，可以这样来做：**从序列中，每次挑选两个不一样的数，从序列中删除，剩下最后的数一定是绝对众数。**  
比如说序列 \[1 2 5 3 3 3 3\]  
删掉(1,2)  
删掉(5,3)  
剩下的都是相同的为所求。

根据这个思路，可以这样做。  
1、对于计算机来说，它只能从头到尾对数组进行遍历，没有办法去挑两两不同的元素，为了模拟上述过程，我们定义一个count和一个表示当前可能成为“多数派”的元素candidate。  
2、.在一次扫描中，如果元素和当前candidate相同则count++，不同则count-–，表示删除一对两两不同元素，当count减为0时，我们就需要更新我们的candidate了。

## 代码 ##

class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int count=0;
            int candidates=nums[0];
            int size=nums.size();
            for(int i=0;i<size;++i)
            {
                if(count==0)
                {
                    candidates=nums[i];
                    count=1;
    
                }
                else
                {
                    if(candidates==nums[i])
                    {
                        ++count;
                    }
                    else
                    {
                        --count;
                    }
                }
            }
            return candidates;
    
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 go求众数

求众数，其中有两种方法： 1. 声明一个map，将遍历的到的数字作为索引，在map中进行+1，最后判断哪个索引对应的数字大于数组长度的一半，则返回索引。 func

旧城等待，/ 2022年12月25日 05:00/ 0 赞/ 132 阅读

相关算法--众数问题

·问题描述：给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如：S=\{1，2，2，2，3，5\}。多重集S

痛定思痛。/ 2022年11月21日 04:25/ 0 赞/ 148 阅读

相关众数问题

众数问题 Time Limit: 2000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述给定含有n个元素的多重集合

た入场券/ 2022年08月18日 02:26/ 0 赞/ 166 阅读

相关众数问题

问题描述：给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。 ★算法设计：对于给定的由n个自然数组成的多重集S，

落日映苍穹つ/ 2022年07月16日 06:51/ 0 赞/ 151 阅读

相关选择绝对众数

绝对众数的概念表示序列中的唯一众数，且出现的次数大于N2，N表示序列的长度。实际上在序列中如果某个数的出现次数超过该序列长度的一半，那么该数一定是唯一的众数。解决这个

墨蓝/ 2022年07月12日 05:08/ 0 赞/ 157 阅读

相关 leetcode 求众数

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

àì夳堔傛蜴生んèń/ 2022年04月23日 09:48/ 0 赞/ 199 阅读

相关众数问题 sdutoj

众数问题 Time Limit: 2000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] [Discuss][

迈不过友情╰/ 2022年03月14日 16:40/ 0 赞/ 169 阅读

相关 leetcode-求众数

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

你的名字/ 2021年12月24日 00:53/ 0 赞/ 280 阅读

相关 LeetCode----------------------求众数

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

绝地灬酷狼/ 2021年12月10日 12:19/ 0 赞/ 233 阅读

相关 leetcode 求众数

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

我不是女神ヾ/ 2021年11月02日 09:18/ 0 赞/ 346 阅读