C++で配列内の重複要素をすべて検出する方法

整数の配列を考えてみましょう。各要素は 1 ≤ a[i] ≤ n(n は配列のサイズ)の範囲にあり、一部の要素は2回出現し、それ以外の要素は1回だけ出現するとします。このとき、配列内に2回出現するすべての要素を見つける必要があります。たとえば、配列が [4,3,2,7,8,2,3,1] である場合、出力は [2, 3] となります。

アルゴリズムの考え方

この問題は「符号反転マーキング」というテクニックを使うことで、余分なメモリをほとんど使わずに解くことができます。要素の値が必ず 1 以上 n 以下であるという制約を利用し、各値をインデックスとして対応する位置の要素の符号を負にすることで、「その値がすでに出現済みかどうか」を記録します。アクセスした位置がすでに負になっていれば、その値は2回目の出現、つまり重複していることが分かります。

計算量は時間 O(n)、追加の空間計算量は出力を除いて O(1) であり、非常に効率的です。

解法の手順

• n を配列のサイズとし、結果を格納するための配列 ans を作成します。
• i を 0 から n−1 まで繰り返します。
  • x に nums[i] の絶対値を代入します。
  • x から 1 を引きます(0始まりのインデックスへ変換)。
  • nums[x] が負であれば、x + 1 を ans に追加します。そうでなければ nums[x] *= -1 として符号を反転させます。
• 最後に ans を返します。

実装例(C++)

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> findDuplicates(vector<int>& nums) {
      int n = nums.size();
      vector <int> ans;
      for(int i = 0; i < n; i++){
         int x = abs(nums[i]);
         x--;
         if(nums[x] < 0) ans.push_back(x + 1);
         else nums[x] *= -1;
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {4,3,2,7,8,2,3,1};
   print_vector(ob.findDuplicates(v));
}

入力

[4,3,2,7,8,2,3,1]

出力

[2,3]