题目描述

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

测试样例:

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

返回:

2

4 5 收藏


直接登录
最新评论
  • 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)复杂度的算法,百度:查找水王,《编程珠玑》里面的一道题

          • 唯心   1 天前

            说的有道理。

            正则效率确实一般。

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

      • 唯心   1 天前

        Snippet

        • ShindouHikaru 目标是全栈~ 16 小时前

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

           

  • 迈克~! 软件开发 1 天前

    上来就用int的可以out了

  • $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 目标是全栈~ 16 小时前

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