首页 > 其他分享 >leetcode 169(摩尔投票)

leetcode 169(摩尔投票)

时间:2024-01-20 11:45:49浏览次数:35  
标签:nums int 复杂度 摩尔 169 众数 vote leetcode

Problem: 169. 多数元素

目录

思路

这里选择采用摩尔投票的方式进行计算众数,这里众数的定义是超过一半的数, 假设众数的票为+1, 负数的票为-1, 则不难得到:

  1. 当目前的票数为0时, 后面的众数仍然是整个数组的众数. 根据这个性质设计算法
  2. 所有数的票面值和为正数

解题方法

初始化众数为nums[0], vote=0, 计算票面值和, 如果vote=0则将众数更新为后一个

复杂度

时间复杂度:

\(O(n)\)

空间复杂度:

\(O(1)\)

Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n=nums.size();
        int count=n/2;
        int vote=0,x=nums[0];
        for (size_t i = 0; i < n; i++)
        {
            if(nums[i]==x) vote++;
            else vote--;
            if(vote==0) x=nums[i+1];
        }
        return x;
    }
};

标签:nums,int,复杂度,摩尔,169,众数,vote,leetcode
From: https://www.cnblogs.com/oxidationreaction/p/17976212

相关文章

  • leetcode 80
    题目描述删除有序数组中的重复项II给你一个有序数组nums,请你原地删除重复出现的元素,使得出现次数超过两次的元素只出现两次,返回删除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。说明:为什么返回数值是整......
  • Leetcode 26 删除数组重复项
    题目描述给你一个非严格递增排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回nums中唯一元素的个数。考虑nums的唯一元素的数量为k,你需要做以下事情确保你的题解可以被通过:更改数......
  • datawhale-leetcode打卡:001-012题
    这次这十二个题目属于是极限肝出来的,有两个参考了一下题解,还是很有意思。我会按照我个人的感觉去写这个东西。螺旋矩阵(leetcode054)这个题目比较恶心的就是跑圈的过程怎么描述。首先,顺时针一圈下来是先从左到右,顶到最右边i<m,好再往下,顶到最下边i<n,好现在i--往回排,最后j--走完一......
  • LeetCode 第 121 场双周赛
    LeetCode第121场双周赛大于等于顺序前缀和的最小缺失整数代码:classSolution{public:intmissingInteger(vector<int>&nums){intn=nums.size();set<int>s;for(autox:nums){s.insert(x);}......
  • leetcode 17.电话号码的字母组合
    leetcode17.电话号码的字母组合第十七题:电话号码的字母组合1.回溯:首先使用哈希表存储每个数字对应的所有可能的字母,然后进行回溯操作。回溯过程中维护一个字符串,表示已有的字母排列(如果未遍历完电话号码的所有数字,则已有的字母排列是不完整的)。该字符串初始为空。每次取电话......
  • 代码随想录算法训练营第一天| LeetCode704 二分查找,LeetCode35,LeetCode34,leetcode27.
    LeetCode704题目链接:704.二分查找-力扣(LeetCode)第一时间的想法:简单来说,二分法给我的印象就是想一条绳子上打很多的结,每次对折正好是一个结点,我们需要找到想要的结点比如(a)代码思路就是不断对折一直到绳子两端重合中间没有结点,最后剩下的就是要找的结点a了。......
  • [ARC169E] Avoid Boring Matches 题解
    题目链接首先考虑无解的情况,一个显然的观察是如果R的个数大于一半,那么无论如何都会出现两个R比赛的情况,小于一半时我们可以调整使得B全都在前面,显然有解。接下来问题变为找到最优可行解,但是状态的合法性不是显然的,我们先尝试判定这个问题。先考虑第一轮比赛,显然我们想让......
  • leetcode 21.合并两个有序链表
    leetcode21.合并两个有序链表第二十一题:合并两个有序链表1.迭代:当l1和l2都不是空链表时,判断l1和l2哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。publicListNodemergeTwoLists(ListNodelist1,......
  • 成为一个合格程序员所必备的三种常见LeetCode排序算法
    排序算法是一种通过特定的算法因式将一组或多组数据按照既定模式进行重新排序的方法。通过排序,我们可以得到一个新的序列,该序列遵循一定的规则并展现出一定的规律。经过排序处理后的数据可以更方便地进行筛选和计算,从而大大提高了计算效率。因此,掌握排序算法是每个程序员的基本功......
  • leetcode 20.有效的括号
    leetcode20.有效的括号第二十题:有效的括号1.栈:判断括号的有效性可以使用「栈」这一数据结构来解决。我们遍历给定的字符串s。当我们遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶......