题目描述:
给你一个含 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]
提示:
-
n == nums.length - 1 <= n <=
-
1 <= nums[i] <= n
进阶:
你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
题目分析:
这道题可以运用数组巧妙的对其求解。利用原有的数组，把所有重复出现的元素转换为索引值，并对此索引值上的元素进行标记，然后再遍历一遍数组，没有标记过的元素其索引值的某种形式就是没有出现过的数字。关键点就是我们要如何对原数组进行标记？这里可行的方案就是把重复出现的数字在原数组出现的位置设为负数，最后仍然为正数的位置即为没有出现过的数。简单点讲，就是遍历数组，把当前出现的元素取绝对值再减去一，因为出现的元素范围是 1 到 n 而索引范围是 0 到 n - 1 ，所以在这里我们要对其进行减一处理。然后通过计算得到的值，找出此值作为索引在数组中的元素，把其变为负数，以示其索引值加一在数组中出现过，最后只需遍历此数组，每个正数元素的索引值加一就是没有在此数组中出现的元素。下面的图给出了 示例 1 标记的过程，可能会更加方便理解上述的过程。
题解:
执行用时: 5 ms
内存消耗: 47.2 MB
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
// 创建结果 list
List<Integer> list = new ArrayList<>();
// 循环遍历数组
for (int num : nums) {
// 获取当前位置上的绝对值 - 1
// 减一是为了把其转换为索引值看待
// 这里使用绝对值是因为我们接下来会把存在当前值 - 1 的索引上元素变为负数
// 负数标记说明其索引 + 1 的元素在数组中出现过
int index = Math.abs(num) - 1;
// 如果索引上的值大于 0
// 则把其变为负数
if (nums[index] > 0) {
nums[index] = - nums[index];
}
}
// 循环遍历更改后的数组
for (int i = 0; i < nums.length; ++i) {
// 如果某个索引上的值大于 0
if (nums[i] > 0) {
// 则证明索引 + 1 的值未在数组中出现过
// 添加到 list 中
list.add(i + 1);
}
}
// 返回结果 list
return list;
}
}题目来源:力扣(LeetCode)