Array-2/DisappearingNumbers.java at a73455ec9fd47936289c73b34ce4006a916b4a50 · super30admin/Array-2 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;

// O(n) time, O(n) space
// class Solution {
//     public List<Integer> findDisappearedNumbers(int[] nums) {
//         List<Integer> ans = new ArrayList<>();
//         Set<Integer> set = new HashSet<>();

//         for (int num : nums) {
//             set.add(num);
//         }

//         for (int i = 1; i <= nums.length; i++) {
//             if (!set.contains(i)) {
//                 ans.add(i+1);
//             }
//         }
//         return ans;
//     }
// }

// O(n) time, O(1) space
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            int idx = Math.abs(nums[i]) - 1; // idx of number

            if (nums[idx] > 0) {
                nums[idx] = nums[idx] * -1;
            }
        }

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