Post

Missing or Repeating

Posted Updated
By Qinghao Hou 1 min read

Find All Numbers Disappeared in an Array

Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public List<Integer> findDisappearedNumbers(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int index = nums[i] - 1;
        while (nums[index] != index + 1) {
            int curr = nums[index];
            nums[index] = index + 1;
            index = curr - 1;
        }
    }

    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            result.add(i + 1);
        }
    }
    return result;
}

Mark

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public List<Integer> findDisappearedNumbers(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }

    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.add(i + 1);
        }
    }
    return result;
}

1
2
3
4
5
6
7
8
9

[4,3,2,7,8,2,3,1]
[4,3,2,-7,8,2,3,1]
[4,3,-2,-7,8,2,3,1]
[4,-3,-2,-7,8,2,3,1]
[4,-3,-2,-7,8,2,-3,1]
[4,-3,-2,-7,8,2,-3,-1]
[4,-3,-2,-7,8,2,-3,-1]
[4,-3,-2,-7,8,2,-3,-1]
[-4,-3,-2,-7,8,2,-3,-1]
algorithm
This post is licensed under CC BY 4.0 by the author.