查找C ++中数组中消失的所有数字

假设我们有一个n个元素的数组。一些元素出现两次，其他元素出现一次。元素的范围是1 <= A [i] <= n。我们必须找到数组中不存在的那些元素。约束是我们必须解决此问题而不使用额外的空间，并且时间将是O(n)。

因此，如果数组为[4，3，2，7，8，8，2，3，1]，则结果将为[5，6]

为了解决这个问题，我们将遵循以下步骤-

• 令n为数组的大小

• 对于i，范围为0至n – 1

• x：= | A [i] | -1

• 如果A [x]> 0，则A [x]：=-A [x]

• 将答案定义为数组

• 对于i，范围为0至n – 1

• 如果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, ]