首页
登录 | 注册

笔试题——微信红包

问题描述:

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

给定一个红包的金额数组gifts及它的大小n,请返回所求红包的金额。

测试样例:
[1,2,3,2,2],5
返回:2
class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        if (gifts.size() != n)
		{
			return 0;
		}

		int last = gifts[0];
		int count = 1;
		for (int i=1; i<n; ++i)
        {
            if (last == gifts[i])
            {
                ++count;
            }
            else
            {
                --count;
                if (count == 0)
                {
                    last = gifts[i];
                    count = 1;
                }
            }
        }

        if (!morethanhalftimes(gifts, last, n))
        {
            return 0;
        }

        return last;
        }
        bool morethanhalftimes(vector<int> gifts, int last, int n)
        {
            int times = 0;
            for (int i = 0; i < n; ++i)
            {
                if (gifts[i] == last)
                    ++times;
            }

            if (times> n / 2)
                return true;
            return false;
        }
};

解题思路是比较法:
	因为有一个数字的次数超过了总数的一半记为last,所以我用了 count 来计算相同数字出现的次数,遍历一遍数组,若相邻(在当前数字的后面的数字)则count加1,若count为0时,则将下一个数字当作是last来遍历,最终若last出现的次数超过一半则说明是,返回他,否则返回0


2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.010 s.
京ICP备10005923号