题目描述

春节期间小明使用微信收到很多个红包,非常开心。在查看领取红包记录时发现,某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现,要求算法尽可能高效。
给定一个红包的金额数组gifts及它的大小n,请返回所求红包的金额。
若没有金额超过总数的一半,返回0。

测试样例:

[1,2,3,2,2],5

返回:

2

4 6 收藏


直接登录
最新评论
  • wx_LGG2sSin   06/02

     

  • 唯心   06/02

    Snippet

    • 唯心   06/02

      Response.Write(result); return;

      放到for里比较好。

    • angelfish   06/03

      这个题目用正则表达式,能高效吗?

      • 唯心   06/06

        正则是非常的高效。

        况且我只单循环,如果匹配直接跳出了。

        你说和双循环比效率差距有多大啊。

      • 唯心   06/06

        如果几万个红包的话,还可以更效率。那就是把数组去重复以后再遍历,效率还会提升大概一倍吧。

        • angelfish   06/06

          正则再高效,也需要遍历一遍源字符串,才能得到匹配结果不是?

          你的代码看起来只有一个for循环,但你是用源字符串hblist中的每个字符,去strhb里面正则查找找到匹配次数的,其实算法的复杂度还是O(n*n)。

          另外:

          if (reg.Matches(strhb).Count >= min)
          result = hblist[i];

          这个if成立一次,就可以跳出循环了,因为这个if只会成立一次。

           

          最后,这个算法有O(n)复杂度的算法,百度:查找水王,《编程珠玑》里面的一道题

          • 唯心   06/22

            说的有道理。

            正则效率确实一般。

            暂时想到的高效的办法就是 二分法。

            • angelfish   06/28

              百度:查找水王,《编程珠玑》里面的一道题。这题就是“查找水王”的一个变种。

      • 唯心   06/22

        Snippet

        • ShindouHikaru 目标是全栈~ 06/23

          这个很简单啊。。。。遍历数组的同时记录每个金额的次数,当某个金额次数等于n/2的时候就可以直接返回那个值了

           

  • 迈克~! 软件开发 06/22

    上来就用int的可以out了

  • 一片糖纸 高级开发工程师 06/23

    $a = [1,2,3,2,2];
    $n = count($a);
    $avg = array_sum($a)/$n;

    while (true) {
    $cur = current($a);
    if ($cur > $avg) {
    echo $cur;break;
    }
    next($a);
    }

  • ShindouHikaru 目标是全栈~ 06/23

    总感觉上面的朋友做的好复杂。。。。  自己用python写了下。。。

     

    • angelfish   06/28

      你这个只是看起来像是O(N)复杂度而已。但是map的put操作和get操作,时间复杂度基本都不是O(1)的,你的算法时间复杂度大于O(N)。

      这题的时间复杂度的下限是O(N),也就是遍历

      • 唯心   06/29

        但是我用 范型的键值对 测试了下。。

        100w模拟数据基本就1秒。。

        啥写法能做到O(N)呢?

      • ShindouHikaru 目标是全栈~ 07/01

        什么叫看起来像,你指出map的操作不是0(1),你这就有意思了,那你的意思是所有算法题的答案里用到map就是错的咯,毕竟大家都不是0(1),所谓的空间换时间不成立咯?或者是真针对py的map咯?真大神啊。。。我服了  期待你写一个你认为的所谓的0(1)的map来打脸

        • angelfish   07/04

          年轻人这么激动干嘛,我说”这题的时间复杂度的下限是O(N)”,也就是说这题用map是达不到O(N)的,而不是说我嫌弃你的map不够高效,我可以弄个更厉害的map出来,OK?

           

          你这算法能得到正确的结果,但是有更优的算法,空间复杂度和时间复杂度都是O(N)的,自己百度“发帖水王”,这是《编程之美》里面一道题。

           

          年轻人不懂多学习,脾气别这么大

  • 南京 李白   06/30

    先对数组做个排序 然后判断第一位和N/2位的值 依次比下去 直到找到

  • JavaScript版本:

     

  • sf705   08/06

    两种方法,时间复杂度都是O(n),剑指offer中有这样的题

    遍历的时候保存两个值,一个是数组中的数result,一个是次数count。如果下一个数等于result,count++,否则count–。如果次数为0了,更改result为当前数据
    用快速排序的思想找到中位数了