Leetcode question 448 Find all missing numbers in the array

)

subject

Here's one for you n Array of integers nums , among nums[i] In the interval [1, n] Inside . Please find out all in [1, n] Range but not in nums Number in , And return the result in the form of array .

Example 1：

Input ：nums = [4,3,2,7,8,2,3,1]
Output ：[5,6]
Example 2：

Input ：nums = [1,1]
Output ：[2]

Tips ：

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
Advanced ： You can use no extra space and the time complexity is O(n) Solve this problem in the case of ? You can assume that the returned array is not included in the extra space .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Answer 1 ： Use extra space for bucket sorting

Is to define an array a, The initial value is 0, Subscript to be i when ,a[i]++;nums[i] by 0, explain i It didn't show up

Explanation 2 ： Modify in place （ Advanced ）

“ Array elements -1” Become a new subscript , The element corresponding to the new subscript is modified , The unmodified subscript is the number that disappears

class Solution {
    
    public List<Integer> findDisappearedNumbers(int[] nums) {
    
        int n=nums.length;
        for(int num : nums){
    
            num =(num-1)%n;// Yes n Take the mold to restore the original value , Why is that ？
            nums[num]+=n;
        }

        List<Integer> result =new ArrayList<Integer>();//ArrayList Of L Be sure to capitalize 

        for(int i=0;i<n;i++){
    
            if(nums[i]<=n){
    
                result.add(i+1);    
            }
        }
        return result;
    }
}