题目描述
思路
原地哈希：
- 找到数字i时，将位置i-1处的数字翻转为负数
- 如果位置i-1上的数组已经为负数，则不进行任何操作
- 再次遍历数组，将数值大于0的元素的下标+1加入到结果集中
方法一：
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i ++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] > 0) nums[index] = -nums[index];
}
for (int i = 0; i < nums.length; i ++) {
if (nums[i] > 0) {
// 那就说明索引i对应的数字i + 1没有出现过
res.add(i + 1);
}
}
return res;
}
}
这段代码用于找到在范围 [1, n] 中未出现在给定数组中的数字。它使用了类似于上一个例子中的技巧，通过修改数组中数字的正负性来标记数字的出现情况。
时间复杂度分析：
- 该代码包含两个循环。第一个循环用于遍历数组并标记出现过的数字，第二个循环用于找出未出现的数字。
- 因此，两个循环的时间复杂度都是 O(n)，其中 n 是输入数组 nums 的长度。
空间复杂度分析：
- 除了用于存储结果的 List res 外，代码没有使用额外的数据结构来存储中间结果。因此，除了输出列表外，额外的空间复杂度是 O(1)。
因此，该算法的时间复杂度为 O(n)，空间复杂度为 O(1)（不包括存储输出结果的空间）。