leetcode第448题，找到所有数组中消失的数字。采用数组元素改变(加或者减)的算法来完成。

LeetCode 448找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

1输入：nums = [4,3,2,7,8,2,3,1]
2输出：[5,6]

示例 2：

1输入：nums = [1,1]
2输出：[2]

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

进阶：

你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

思路

给数组中的元素加某个值或者把数组中的元素变成负数

  1. 移动指针从数组头部开始，去除指针所指的元素，让其减1使得变成从[0, n-1]的下标。
  2. 找到指针所指的元素相同的下标，把下标所指的元素值改成负数。
  3. 从数组头部开始遍历整个数组，每次找到对应指针所指的元素相同的下标所指的元素，改成负数。如果已经改成负数，则忽略。
  4. 再次遍历整个数组，查看没有成为负数的下标，这些值在数组中没有出现过，对应下标+1则为[1,n]的返回结果

解题

 1class Solution {
 2    //对整个数组相加或者相减，第二次遍历找出没有发生变化的元素下标
 3    public List<Integer> findDisappearedNumbers(int[] nums) {
 4        int n = nums.length;
 5        for(int i = 0; i < n; i++)
 6        {
 7            int x = (nums[i] - 1) % n;//这里的取余操作还原本来的值
 8            nums[x] += n;
 9        }
10        List<Integer> res = new ArrayList<Integer>();
11        for(int i = 0; i < n; i++)
12        {
13            if(nums[i] <= n)
14            {
15                res.add(i + 1);
16            }
17        }
18        return res;
19    }
20}