首页 > 试题广场 >

微信红包

[编程题]微信红包

热度指数：34578 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

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

若没有金额超过总数的一半，返回0。

数据范围： $1 \le n \le 1000 \$ ,红包金额满足 $1 \le gift_i \le 100000\$

示例1

输入

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

输出

示例2

输入

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

输出

算法知识视频讲解

ReklawPeels

注意，此题的输入中，不一定有数字出现的次数超过一半，比如一个测试用例134个数，有一个数字出现了67次，而不是68，要求返回0

遍历一遍数组，用一个哈希表存每个数字出现的次数

再遍历一遍哈希表，有次数超过一半的就返回，否则返回0

using System.Collections.Generic;
class Gift
{
    public int getValue(int[] gifts, intn)
    {
        Dictionary<int, int> Gifts = new Dictionary<int,int>();
        for(int Index = 0; Index < n; Index++)
        {
            if(!Gifts.ContainsKey(gifts[Index]))
                 Gifts.Add(gifts[Index], 1);
            else
                Gifts[gifts[Index]]++;
        }
        foreach(KeyValuePair<int, int> Pair in Gifts)
        {
            if(Pair.Value > n / 2)
                return Pair.Key;
        }
        return 0;
    }
}

编辑于 2016-03-26 00:11:32 回复(0)

Python

华科平凡

python两行代码的解法如下，当然也可以压缩成一行，我就不***了。

from collections import Counter

class Gift:
    def getValue(self, gifts, n):
        a = Counter(gifts).most_common(1)[0]
        return a[0] if a[1] > n // 2 else 0

发表于 2017-09-12 14:44:55 回复(4)

DarcyX

先排序再找中间值的方法不是最高效的，最高效的应该是O(n)。寻找水王的经典题

class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        int rslt = gifts[0];
        int cnt = 1;
        int nums = 0;
        if(1 == n)
            return rslt;
        for(int i = 1;i < n;++i) {
            if(0 == cnt) {
                rslt = gifts[i];
                cnt = 1;
                continue;
            }
            if(gifts[i] == rslt)
                ++cnt;
            else {
                --cnt;
            }                
        }
        for(int i = 0;i < n;++i) {
            if(rslt == gifts[i])
                ++nums;
        }
        if(nums > n/2)
            return rslt;
        else
            return -1;
    }
};

发表于 2016-05-22 11:36:08 回复(0)

方秋然

count  = [gifts.count(gift) for gift in gifts]
return gifts[count.index(max(count))] if max(count)> n/2   else 0

Python两行解决

编辑于 2018-03-24 11:43:11 回复(1)

~一念执着~

众数问题，摩尔投票法
class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        int cnt=0;
        int tmp;
        for(int i=0;i<n;i++){
            if(cnt==0||gifts[i]==tmp){
                if(cnt==0)
                    tmp=gifts[i];
                cnt++;
            }
            else cnt--;
        }
        cnt=0;
        for(int i=0;i<n;i++){
            if(gifts[i]==tmp)
                cnt++;
        }
        if(cnt>n/2)
            return tmp;
        else
            return 0;
    }
};

发表于 2017-07-05 14:31:12 回复(0)

见过凌晨4点洛杉矶

class Gift {
public:
	int getValue(vector<int> gifts, int n) {				
		int i = 0;
		int j = 1;
		int temp = gifts[0];//初始化，temp先保存第一个数字
		int count = 1;//count初始化1，表示有1个相同的数字
		while (j<n)
		{
			if (count == 0)
			{				
				temp = gifts[j];
				count++;
				j++;
			}
			if (j >= n) 
				break;
			if (temp == gifts[j])
			{
				count++;
				j++;
			}
			else
			{
				count--;
				j++;
			}
		}

		if (count == 0) //count==0，不存在
		{
			return 0;
		}

		//但是count!=0，并不能说明不存在，因为我们要判断temp是不是有一半以上。
		count = 0;
		for (int i = 0; i < n; i++)
		{
			if (gifts[i] == temp)
				count++;
		}
		return (count > n / 2 ? temp : 0);
	}
};

发表于 2016-09-07 01:49:33 回复(0)

C/C++

Glenn_Gould


	int getValue(vector<int> gifts, int n)



	{



	map<int,int> r;



	for(int i = 0; i < n; i++)



	if(++r[gifts[i]]>n/2)



	return gifts[i];



	return 0;



	}

编辑于 2016-08-31 21:57:37 回复(0)

sharpdeep

《编程之美》里“寻找水王”一章一样的题。最佳算法是每次都去除不一样的数字，最后剩下来的就是那个超过一半金额

发表于 2015-10-09 18:53:22 回复(8)

百步飞剑-盖聂

import java.util.*;
public class Gift {
    public int getValue(int[] gifts, int n) {
        // write code here
        int money=0;
        TreeMap<Integer,Integer> map=new TreeMap<Integer,Integer>();
        for(int i=0;i<n;i++){
            if(n>1){
                if(map.get(gifts[i])==null)
                    map.put(gifts[i],1);
                else{
                    int number=map.get(gifts[i]).intValue();
                    number++;
                    if(number>n/2)
                        return money=gifts[i];
                    map.put(gifts[i],number);
                }
            }
        }
        return money;
    }
}

发表于 2016-03-29 23:39:40 回复(0)

雾海-

#include <algorithm>
class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        //先排序一下,然后判断一下中间的数与1/4处数或3/4处数是否相同,若相同则返回此数
        //若不相同,则返回0
        sort(gifts.begin(),gifts.end());
        int half = n/2;
        int start = n/4;
        int last = start*3;
        if((gifts[start]==gifts[half])||(gifts[half]==gifts[last])){
            return gifts[half];
        }else{
            return 0;
        }
    }
};

发表于 2022-03-19 19:44:47 回复(0)

w浩

第一反应使用hash_map也能线性解决问题

class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        int mid = (n+1)/2;
        unordered_map<int,int> map;
        for(int i = 0;i<n;i++){
            map[gifts[i]]++;
        }
        
        for(auto it=map.begin();it!= map.end();it++){
            if(it->second >= mid) return it->first;
        }
        
        return 0;
        
    }
};

发表于 2020-12-26 14:18:56 回复(0)

black_mamba

   int getValue(vector<int> gifts, int n) {
        // write code here
        int len=gifts.size()/2;
        for(int i=0;i<gifts.size();++i)
        {
            if(count(gifts.begin(),gifts.end(),gifts[i])>len)
            {
                return gifts[i];
            }
        }
        return 0;
    }

   stl count()大法好

编辑于 2020-08-14 01:10:49 回复(0)

巫山云201907201442429

C++ 代码，不知道是不是钻了漏洞，各位大神看看

class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        sort(gifts.begin(), gifts.end());
        if (gifts[n/4] == gifts[n/2] || gifts[3*n/4] == gifts[n/2])
            return gifts[n/2];
        return 0;
    }
};

既然超过了一半，那么排序后，中位数肯定是最多出现的不用说，而且肯定会覆盖【1/4，2/4】，【2/4,3/4】这两个区间中的一个，举例：7个数字【1,2,3,3,3,3,5】

发表于 2020-05-08 23:03:41 回复(0)

小周好饿

class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        //有可能不存在
        int count=0;
        sort(gifts.begin(),gifts.end());
        for(int i=0;i<n;i++)
        {
            if(gifts[i]==gifts[n/2])
                count++;
        }
        return (count>n/2)?gifts[n/2]:0;
    }
};

发表于 2019-12-03 12:21:39 回复(0)

C/C++

赫菲斯托斯

class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        int ret = gifts[0];
        int count = 1;
        for(size_t i = 1; i<n; ++i)
        {
            if(count==0)
            {
                ret = gifts[i];
                count = 1;
            }
            else if(ret == gifts[i])
                count++;
            else
                count--;

        }
        return count==0 ? 0 : ret;
    }
};

这个解法有什么问题，求大神解决！！！

解题思路：如果数组中存在一个数字出现的次数多于数组的一半时，只需遍历一遍；

在遍历过程中，保存两个值，一个是数组中的数字，另一个是次数。

遍历到下一个数字时，如果下一个数字与保存的数字相等，那么次数+1；

如果下一个数字与保存的数字不相同，次数-1；

如果次数为0，将要这个数字设置为要保存的数，并且将次数设为1；

因为我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么最后保存的数一定是出现次数大于数组个数的一半。

编辑于 2019-12-02 22:12:22 回复(0)

skrskr66

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

之前做题就做到过类似的，出现最多的大于总数的二分之一，那么排序之后，一定在中间数或者前一位

发表于 2019-06-14 14:00:22 回复(0)

天天看西瓜

classGift {

	public:



	    int getValue(vector <int>  gifts, int n) {



	        sort(gifts.begin(),gifts.end());



	        for(int i=0;i<n/2;i++)



	        {



	            if(gifts[i] == gifts[i+n/2])



	                return gifts[i];



	        }



	        return 0;



	    }

}

编辑于 2019-04-10 11:20:28 回复(0)

kestars

import java.util.*;

public class Gift {
    public int getValue(int[] gifts, int n) {
        // write code here
        HashMap<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
        int half=n/2;
        for(int i=0;i<n;i++){
            if(hashMap.get(gifts[i])==null){
                hashMap.put(gifts[i],1);
            }else{
                int count=hashMap.get(gifts[i])+1;
                if(count>half)
                    return gifts[i];
                hashMap.put(gifts[i],count);
            }
        }
        return 0;
    }
}

发表于 2018-10-13 09:46:50 回复(0)

BOOMBAOZI

//使用map记录出现的次数
public static int getValue(int[] gifts, int n) {
    Map<Integer, Integer> map = new HashMap();
    Integer re = gifts[0]; int max = 0; for (int i = 0; i < gifts.length; i++) { if (map.containsKey(gifts[i])) {
            map.put(gifts[i], map.get(gifts[i]) + 1);
        } else {
            map.put(gifts[i], 1);
        } if (map.get(gifts[i]) > max) {
            max = map.get(gifts[i]);
            re = gifts[i];
        }
    } if (max > gifts.length / 2) { return re;
    } else { return 0;
    }
}

发表于 2018-08-28 17:21:59 回复(0)

mybaties

import java.util.*;

public class Gift {
    public int getValue(int[] gifts, int n) {
        // write code here
        
        TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
        for(int i = 0;i < gifts.length;i++){
            Integer key = new Integer(gifts[i]);
            if(map.get(key) == null){
                map.put(key,1);
            }
            else{
                int value = map.get(key).intValue();
                value++;
                map.put(key,value);
                if(value >(double)n*1.0/2)return key.intValue();
            }
        }
        return 0;
    }
}

采用了树型图，还看了书.

发表于 2018-08-17 00:00:10 回复(0)