虾皮一道面试算法题

虾皮9/10正式批二面算法题

一些学生分享了与他同一天生日的其他同学的数量，根据这些回答，判断最少有多少学生。

提示：

1.一年最多有366天，输入中最多只会有366种不同的答案；

2.同一天出生的学生不会超过1000人，输入的每个数字范围为[0，1000]；

3.分享的学生可能是所有学生，也可能没有学生分享

样例

输入：[3,2,2,2]，输出7

输入：[1,1,1]，输出4

输入：[1]，输出2

其实这是leetcode原题781

class Solution {
public:
    int numRabbits(vector<int>& answers) {

        /*大佬分享的版本
        const int maxn=1e5+10;
        int n,b[maxn],ans=0;
        n=answers.size();

        vector<int> a(n+1);
        for(int i=1;i<=n;i++){
            a[i]=answers[i-1];
        }

        for(int i=1;i<=n;i++){
            b[a[i]]++;
        } 
        for(int i=1;i<=n;i++){
            if(b[a[i]]!=0){
                int cnt=b[a[i]];
                int pos=a[i];
                while(cnt>(pos+1)){
                    ans+=(pos+1);
                    cnt-=(pos+1);
                }
                if(cnt!=0){
                    ans+=(pos+1);
                }
                b[pos]=0;
            }
        }
        if(ans>366){
            return 366;
        }else{
            return ans;
        }
        */

        /*按自己思路写的版本
        int n=answers.size();
        sort(answers.begin(), answers.end());
        int res=0;

        int i=0, j=0;

        while(i<n && j<n){
            res+=answers[i]+1;

            j=min(i+answers[i], n-1);

            j++;i=j;
        }

        return res;
        */

        //参考题解分类的版本
        unordered_map<int, int> count;
        int res = 0;
        for ( int answer : answers ) {
            if ( count[answer] == 0 ) { // 需要新开一个分组了
                res += answer + 1;
                count[answer] = answer;
            } else {                    // 属于已有的分组，还可以喊这个数字的兔子要减一
                --count[answer];
            }
        }
        return res;

    }
};