微信红包(C++、Python)

腾讯2016招聘笔试：微信红包

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

数据范围：
，

示例1
输入：

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

输出：

2

示例2
输入：

[1,1,2,2,3,3],6

输出：

0

Tips1：以下所有代码经过实测提交可以AC，大家请放心阅读
Tips2：由于提交测试的平台没有ACM模式，只有核心代码模式，也就是把要处理的数据都已经放入容器里了，直接写逻辑就行。所以可能和平时的写法不太一样，看不习惯的话大家多包涵

思路一（排序法，时间复杂度O(Nlog(N))，空间复杂度O(N)）

常规思路，先对数组排序，再找出中位数，计算出值与中位数相等的数字个数，如果超过了数组长度的一半，则返回中位数，否则返回0

C++代码：

class Gift {
  public:
    int getValue(vector<int> gifts, int n) {
        int cnt = 0;
        sort(gifts.begin(), gifts.end());
        for (int i = 0; i < n; i++) {
            if (gifts[i] == gifts[n / 2])
                cnt++;
        }
        if (cnt > n / 2)
            return gifts[n / 2];
        return 0;
    }
};

Python代码

class Gift:
    def getValue(self, gifts, n):
        cnt = 0
        gifts.sort()
        for i in range(n):
            if gifts[i] == gifts[n / 2]:
                cnt += 1
        if cnt > n / 2:
            return gifts[n / 2]
        return 0

思路二（哈希映射法，时间复杂度O(N)，空间复杂度O(N)）

建立哈希表找其中出现次数大于n/2的数

C++代码

class Gift {
  public:
    int getValue(vector<int> gifts, int n) {
        unordered_map<int, int> mp;
        for (auto num : gifts) {
            mp[num]++;
            if (mp[num] > n / 2)
                return num;
        }
        return 0;
    }
};

Python代码

class Gift:
    def getValue(self, gifts, n):
        dic = dict()
        for num in gifts:
            dic[num] = dic.get(num, 0) + 1
            if dic[num] > n / 2:
                return num
        return 0

思路三（调用库函数，时间复杂度不太清楚，空间复杂度O(N)）

Life is short，You need python

Python代码：

class Gift:
    def getValue(self, gifts, n):
        if gifts.count(max(gifts, key=gifts.count)) > n / 2:
            return max(gifts, key=gifts.count)
        else:
            return 0

212丨acc丨2022.12.06