2016校招真題プログラミング練習——微信お年玉(テンセント)

タイトルの説明
春節の間、明ちゃんは微信を使ってお年玉をたくさんもらって、とても楽しかったです.お年玉の受け取り記録を見ると、あるお年玉の金額がお年玉の総数の半分を超えていることがわかりました.明ちゃんにこのお年玉の金額を見つけてください.具体的なアルゴリズムの構想とコードの実現を書き出して、アルゴリズムができるだけ効率的であることを要求します.お年玉の金額配列giftsとその大きさnを指定し、求めたお年玉の金額を返してください.金額が合計の半分を超えていない場合は、0を返します.テストサンプル:

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

戻る:2
考え方:出现した金额と対応する数量をすべて1つの2次元のvectorの中に置いて、実は复雑度はきっと最适化することができて、2ブラシの时に更にやって、更に出现回数の最も多いと総数の半分を比较して、结果を得ることができます~
コード:

class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // write code here
        vector<vector<int> >res{ {0,0} };
        int max=n/2;//     
        int output=0;
        int flag = 0;//res           
        for (int i = 0; iint size = res.size();
            for (int j = 0; j < size; ++j){
                if (res[j][0] == gifts[j]){//              ，          1
                    res[j][1] += 1;
                    flag = 1;//     1，      
                    break;
                }
            }
            if (flag == 0){//      0，         res ，   1
                res.push_back({ gifts[i], 1 });
            }
        }
        int size_res = res.size();
        for (int i = 0; i < size_res; ++i){
            if (res[i][1]>max){//                
                output = res[i][0];//         ，     
                break;
            }
        }
    return output;
    }
};

出力結果:運転時間:7 msメモリ使用量:496 K状態:正解