【C++刷题】力扣-#448-找到所有数组中消失的数字
题目描述
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例
示例1:
输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
示例2:
输入：nums = [1,1]
输出：[2]
题解
这个问题可以通过一次遍历来解决，使用数组的索引作为标志位来标记已经出现过的数字。
- 遍历数组：遍历整数数组 nums。
- 标记数字：对于每个数字 num，通过将 nums[num - 1] 的绝对值取反来标记该数字已经出现过。如果该位置已经是负数，说明该数字已经标记过，因此是出现两次的数字。
- 收集结果：再次遍历数组，收集所有出现两次的数字。
代码实现
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> result;
for (int num : nums) {
int index = abs(num) - 1;
if (nums[index] >= 0) {
nums[index] = -nums[index];
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > 0) {
result.push_back(i + 1);
}
}
return result;
}
复杂度分析
● 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们需要遍历一次数组来标记数字，再遍历一次来收集结果。
● 空间复杂度：O(1)，因为我们只使用了常数个额外变量。
这个算法的优势在于它不需要额外的存储空间，并且时间效率较高。