leetcode [#448]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

---

解决方案

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new LinkedList<>();
        int n = nums.length;
        for(int i = 0; i < n; i++){
            nums[(nums[i] - 1) % n] += n;
        }
        for(int i = 0; i < n; i++){
            if(nums[i] <= n){
                list.add(i+1);
            }
        }
        return list;
    }
}

---

注意事项

1. 实质上要将数组中的每一个元素看做存储的是该数组的下标（每个数需要减1）
2. 遍历一遍，取到每个数组元素的值，将其看做下标的情况下，将该数组对应位置加n
3. 凡是在该数组不存在的元素（指范围1-n）内，对应下标的值就无法被加n（一次或多次加n都不可能）
4. 再遍历一遍，找到现在元素值小于等于n的就是缺失的元素