すべてのお年玉の中で出現回数がお年玉の総数の2分の1より大きい-筆記試験シリーズ2
1309 ワード
テーマ:お正月、白さんはたくさんのお年玉を手に入れて、すべてのお年玉の中でお年玉の総数の2分の1以上の金額を見つけるように要求しました.アルゴリズムとコードを書き出します
抽象的なテーマは:1組の数の中で、ある出現回数が総数字の半分を超える数字を探します
Tips:hashmap
すべてのお年玉の出現回数を統計し、要求を満たす金額数が現れると統計を停止するhashテーブルを作成できます.
検索するのはすべてのお年玉のうち、出現回数がお年玉の総数の一般的な金額より大きいため、関数cashのif文では、その回数が条件を満たす限りループしません.
実は私が理解しているポイントは、ハッシュ表です.
C++の関数unordered_mapは、unorderedハッシュコンテナ(hash container)が非常に重要なコンテナタイプであり、通常、ツリーのストレージ方式よりも高いアクセス効率を提供することができる.
ありがとう:DeYuanZhang、私の元のコードの中のバグを指摘して、今現れたのは修正した後の形式です
以前のバージョンでは、double-->charが問題になりました.doubleは8 bytes、charは1バイトなので、変換中に上位カットの問題が発生しました.
抽象的なテーマは:1組の数の中で、ある出現回数が総数字の半分を超える数字を探します
Tips:hashmap
すべてのお年玉の出現回数を統計し、要求を満たす金額数が現れると統計を停止するhashテーブルを作成できます.
#include "stdafx.h"
#include <iostream>
#include<vector>
#include <unordered_map>
#include <string>
using namespace std;
string cash(vector<string> &num){
unordered_map<string, int> mymoney;
int flag = 0;
for (int i = 0; i < num.size(); i++){
mymoney[string(num[i])]++;
if (mymoney[string(num[i])] > num.size() / 2){
flag = i;
break;
}
}
if (!flag){
return "Not Find!";
}
return num[flag];
}
int main(){
string c[6] = { "11.001", "11.1", "11.113", "11.1", "11.1", "11.12" };
vector<string> a(c, c + 6);
cout << cash(a) << endl;
}
検索するのはすべてのお年玉のうち、出現回数がお年玉の総数の一般的な金額より大きいため、関数cashのif文では、その回数が条件を満たす限りループしません.
実は私が理解しているポイントは、ハッシュ表です.
C++の関数unordered_mapは、unorderedハッシュコンテナ(hash container)が非常に重要なコンテナタイプであり、通常、ツリーのストレージ方式よりも高いアクセス効率を提供することができる.
ありがとう:DeYuanZhang、私の元のコードの中のバグを指摘して、今現れたのは修正した後の形式です
以前のバージョンでは、double-->charが問題になりました.doubleは8 bytes、charは1バイトなので、変換中に上位カットの問題が発生しました.