blog

最頻出要素

配列を一度繰り返し、すべての要素の出現回数のハッシュを作成します。\nクラス Solution {\npublic.\n int { {.\n unor...

Feb 16, 2020 · 2 min. read
シェア

配列を一度繰り返し、すべての要素の出現回数をハッシュ化します。

class Solution {
public:
 int majorityElement(vector<int>& nums) {
 unordered_map<int, int> hash;
 int size = nums.size();
 for(int num : nums) {
 ++hash[num];
 if(hash[num] > size / 2) {
 return num;
 }
 }
 return 0;
 }
};

上記のアプローチはO(n)の時間と空間の複雑さを持ちますが、O(n)の時間とO(1)の空間の複雑さを持つ別のアプローチもあります。

配列を1回走査した後、curNumは配列の長さの半分以上の出現回数を記録します。

このアルゴリズムはありえないように見えますが、なぜ正しいのでしょうか?配列をトラバースした後のcurNumの値が、配列の長さの半分以上の回数でないと仮定して、反実仮想法を使えばよいのです。つまり、配列に現れる真の回数は0に打ち消されることになり、配列の少なくとも半分の数値が異なることになり、問題の意味と矛盾するので、このアルゴリズムは正しいことになります。

コードは以下の通り:

class Solution {
public:
 int majorityElement(vector<int>& nums) {
 if(nums.size() == 0) {
 return 0;
 }
 if(nums.size() == 1) {
 return nums[0];
 }
 int curNum = nums[0],t = 1; //まず、0番目の数字が最頻出であるとみなされる。
 for(int i = 1; i < nums.size(); ++i) {
 if(nums[i] == curNum) { //現在の数字が最大の数字とみなされたら、よし、次だ!
 +t;
 } else {
 -t; //異なる数字を見つけ、オフセットする
 ift == 0) { //オフセットが0になったら、もしかしたら探している数字は出現回数が最も多い数字ではないかもしれないという事実を反省するときである。
 curNum = nums[i];
t = 1;
 }
 }
 }
 return curNum;
 }
};
Read next