アルゴリズムの整理——2015テンセント開発のペンの試験問題

春節の間、明ちゃんは微信を使ってお年玉をたくさんもらって、とても楽しかったです.お年玉の受け取り記録を見ると、あるお年玉の金額がお年玉の総数の半分を超えていることがわかりました.明ちゃんにこのお年玉の金額を見つけてください.具体的なアルゴリズムの構想とコードの実現を書き出して、アルゴリズムができるだけ効率的であることを要求します.
アルゴリズム:転送ドア
このアルゴリズムは,一般にO(nlogn)時間の複雑さを必要とする結果をO(n)に良く減少させるが,最も多く出現する数の出現回数が(等しくない)集合中の個数の半分より大きいことが前提である.

float mostElement(vector v){
	int count = 0;
	float m;
	for(int i=0;i

このアルゴリズムの鍵はcount++,count--にある.最大出現回数の値をaと仮定し、遍歴時にm=aとなると、新しいaに遭遇すると促進作用を果たす.m!=aの場合、新しいaは消極的な役割を果たす.aの個数は集合個数の半分より大きいため,最後にcountは必ず0より大きく,m=aである.
1組の数の符号化において、任意の2つの隣接する符号が1ビットのバイナリ数だけ異なる場合、この符号化をグレイコード(Gray Code)と呼ぶ.再帰法を用いてNビットのグレイコードを生成し,この関数の頑丈性を保証する関数を作成してください. 
ウィキペディアからの解法:転送ゲート
2進数0の値を持つグレイ符号は0項目、1項目は右端のビットを変更し、2項目は右端から1番目のビットの左端のビットを変更し、3、4項目は1、2項目と同じ方法で繰り返し、n個のビットのグレイ符号を並べることができる.
コードは、グレイ符号数mがビット数nと関係があるため、上の2ステップを1サイクルとする.ループから飛び出す境界条件は,第2項に左ビットがないことである.コードの頑丈さは、必要なビット数が大きい場合でも正しく出力できるような気がします.

void grayCode(int n){
	int* grays = new int[n];
	for(int i=0; i