专栏首页Effective Objective C那些年刷力扣遇到的坑:众数问题
原创

那些年刷力扣遇到的坑:众数问题

LeetCode39.png

这道试题出现在《剑指Offer》和LeeCode中,有两种高效的解法:

- 方法一

前提:

存在众数,则中位数一定是众数。

解释:

该方法利用快排中 partition 操作查找中位数,即根据 partition 操作数的 index 判断是否为中位数,循环:若 index == len/2即为中位数,结束循环;index < len/2 时,中位数在 index 右边,将 begin = index+1,继续 partition;index > len/2 时,中位数在 index 左边,将 end = index-1,继续 partition,直到循环结束。根据中位数统计出现次数,判断是否为众数。

Partition实现:

在实现 partition 的时候,有两种思路,一种使用单向指针,一种使用双向指针查找修改,两种思路都是先选出一个操作数 keyNum,遍历数组,将数组分为小于 keyNum 和大于 keyNum 的两部分。

单向指针:

用 small 指针指向小于 keyNum 的索引,初始值为 begin-1;遍历过程中,出现小于 keyNum 的数,small+1后,将其和 small 所指的位置进行交换,当固定了数组中所有小于 keyNum 的数,大于该数的数也就固定了。

双向指针(遇坑):

错误❌解法:我分别用 begin 和 end 两个指针指向数组首尾,用 begin++ 向后查找大于 keyNum 的数,用 end-- 向前查找小于 keyNum 的数,然后将其交换,当 begin >= end 的时候跳出循环。begin 指向的下一个位置即keyNum 所在位置。而这种方法看似无误,实际上不适合这种问题——在 partition 的过程中,将数组分为两半之后,需要将操作数插入数组中,而 begin 和 end 在执行过程中并没有将 keyNum 的位置留出来。

因此正确解法,应是当我们选出操作数之后,比如 0 位置的数,将其保存下来作为 keyNum。这时 0 位置就可以空出来了,可以用 end-- 向前查找小于 keyNum 的数,与 begin++ 进行交换;然后用 begin++ 向后查找大于等于 keyNum 的数,与 end-- 进行交换, 当begin >= end 的时候跳出循环。此时 begin 所在位置为 keyNum 位置。

示例代码

int majorityElement(vector<int>& nums) {
    int len = nums.size();
    if(len == 1){
        return nums[0];
    }
    int mid = len >> 1;
    int begin = 0, end = len - 1;
    // cout<<"mid ="<<mid<<endl;
    int index = partition(nums, len, begin, end);
    while(index != mid){
        if(index > mid){
            end = index - 1;
            index = partition(nums, len, begin, end);
        } else if(index < mid){
            begin = index + 1;
            index = partition(nums, len, begin, end);
        }
    }
    int result = nums[index];
    // if(checkMajorityNumber(nums, len, result)){
    //     return result;
    // }
    return result;
}
int partition(vector<int>& nums, int len, int begin, int end){
    int key = begin;
    int keyNum = nums[key];
    while(begin < end){
        while(nums[end] >= keyNum && begin < end){
            end--;
        }
        if(begin < end){
            nums[begin++] = nums[end];
        }
        while(nums[begin] < keyNum && begin < end){
            begin++;
        }
        if(begin < end){
            nums[end--] = nums[begin];
        }
    }
    swap(keyNum, nums[begin]);
    return begin;
}

- 方法二(摩尔投票法)

前提:

由于众数出现的次数超过数组长度的一半;若记众数的票数为 +1,非众数的票数为 -1,则一定有所有数字的票数和>0 。

解释:

假设数组 nums 中存在众数为 x,数组长度为 len。若 nums 的前 a 个数字的票数和 =0,则数组后 len-a 个数字的票数和一定仍 >0,即后 len-a 个数字的众数仍为 x。

示例代码

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

测试用例

中位数不存在,中位数存在,数组为空,数组不存在。

参考资料

[1] https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 那些年遇到的刁钻JavaScript面试题(可防踩坑)

    解析: 这是比较常规的面试题了,主要考察的是 JavaScript 中的隐式类型转换。在 JS 中 + 主要有两个作用:数字相加和字符串拼接,当 + 两边不都为...

    MudOnTire
  • 微信刷卡支付API详解

    最近因项目需要微信支付,通过扫码抢扫描微信付款码,调用微信刷卡支付API完成扣费,过程中遇到了遇到了一些问题,填了很多坑,所以把自己的经验分享给大家,本篇文章介...

    南风
  • 晋江市各中学开始使用腾讯微校电子校园卡了

    ? 在晋江市多所中学食堂的午餐时间,同学们正在依次刷卡用餐。在与以往相同的操作背后,支撑的用餐体系,已经实现了静默升级,腾讯微校电子校园卡全面进驻。 ? 晋江...

    鹅老师
  • 短信代收,一个年产数亿的黑产链条

    陈梦 腾讯安全平台部高级安全产品经理 我将会通过一个系列文章来给大家揭开这里的神秘面纱,看看究竟是谁坑走了创业者的钱。今天来看第一篇——年产值过亿的短信代收...

    腾讯研究院
  • 微信刷卡支付API详解

    南风
  • 算法八股,简历项目,在校小白如何冲击大厂?快上车,我有!

    上海 985 计算机专业大三在读,有 acm 经验,无牌子,有一些算法竞赛和数模小奖,写在简历上的都是课程项目。

    ACM算法日常
  • 张小龙发布2018微信计划 | QQ 推出「玩一玩」小游戏平台

    轻松一刻 ? 漫画来自于西乔《神秘的程序员们》 01 张小龙现场“约战”跳一跳,发布2018微信全新计划 2017 年 1 月 15 日,微信公开课 PRO 版...

    极乐君
  • 刚开始学编程?这几款小技巧能让你事半功倍

    回顾我这三年的工作历程,总结了一些自己在开发过程中遇到的问题以及学习方法,如果你也遇到了,这篇文章可能可以给你一些建议或者参考。

    王小婷
  • 刚开始学编程?这几款小技巧能让你事半功倍

    回顾我这三年的工作历程,总结了一些自己在开发过程中遇到的问题以及学习方法,如果你也遇到了,这篇文章可能可以给你一些建议或者参考。

    王小婷

扫码关注云+社区

领取腾讯云代金券