数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中查找数组中所有消失的数字
假设我们有一个包含 n 个元素的数组。一些元素出现两次，另一些元素出现一次。元素的范围是 1 <= A[i] <= n。我们必须找到数组中不存在的那些元素。约束条件是我们必须在不使用额外空间的情况下解决此问题，并且时间复杂度为 O(n)。
因此，如果数组为 [4, 3, 2, 7, 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, ]
更新于： 2020-04-28
371 次浏览
广告