LeetCode.448.Find All Numbers Disappeared in an Array 数组中消失的数

题目描述

448 Find All Numbers Disappeared in an Array
https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/

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]

---

解题过程

相似题目
LeetCode.448.Find All Numbers Disappeared in an Array 数组中消失的数
LeetCode.442.Find All Duplicates in an Array 数组中所有重复的数
LeetCode.645.Set Mismatch 找出数组中重复的数和缺失的数
LeetCode.041.First Missing Positive 数组中缺失的第一个正数

一看到题干中的 1 ≤ a[i] ≤ n ，就知道肯定是用数组下标技巧做。
原地哈希，在输入数组本身以某种方式标记已访问过的数字，对于数据中的每个值 a[i] ，将值 a[a[i]] 取反来表示这个值出现过 。
时间复杂度 O(n)，空间复杂度 O(1)

private static class SolutionV2020 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            nums[Math.abs(nums[i]) - 1] = - Math.abs(nums[Math.abs(nums[i]) - 1]);
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                list.add(i + 1);
            }
        }
        return list;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_448_FindAllNumbersDisappearedInArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_448_FindAllNumbersDisappearedInArray.java

---