C++で配列に表示されなくなったすべての数値を検索する

n個の要素の配列があるとします。一部の要素は2回表示され、他の要素は1回表示されます。要素は範囲1<=A [i]<=nにあります。配列に存在しない要素を見つける必要があります。制約は、余分なスペースを使用せずにこの問題を解決する必要があり、時間はO（n）になるということです。

したがって、配列が[4、3、2、7、8、2、3、1]の場合、結果は[5、6]

これを解決するには、次の手順に従います-

• nは配列のサイズです
• 0からn–1の範囲のiの場合
  • x：=| A [i] | -1
  • A [x]> 0の場合、A [x]：=--A [x]
• 答えを配列として定義する
• 0からn–1の範囲のiの場合
  • A [i]> 0の場合、答えにi+1を追加します
• 答えを返す

例

理解を深めるために、次の実装を見てみましょう-

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

入力

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

出力

[1, 6, ]