LeetCode:448.找到所有數組中消失的數字

題目：

給定一個範圍在  1 ≤ a[i] ≤ n ( n = 數組大小 ) 的 整型數組，數組中的元素一些出現了兩次，另一些隻出現一次。

找到所有在 [1, n] 範圍之間沒有出現在數組中的數字。

您能在不使用額外空間且時間複雜度為O(n)的情況下完成這個任務嗎? 你可以假定傳回的數組不算在額外空間内。

示例:

輸入:
[4,3,2,7,8,2,3,1]

輸出:
[5,6]
           

源碼：

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // 先把每個數放在它該出現的位置
        // 例如 1 應該被放在下标為 0 的位置，如果下标為 0 的位置已經是 1 了
        // 那麼說明 1 重複出現了，此時将這個數設定為 -1
        // 最後再次周遊數組，将數字為 -1 的元素設定為 該下标 + 1 就是原本正确的數字
        for (int i = 0; i < nums.length;) {
            int pos = nums[i];
            // pos 等于 i + 1 說明該位置的正确數字就是 pos
            // pos 等于 -1 說明之前已經将某個數設定為了 -1
            // 繼續周遊下一個數字
            if (pos == -1 || i == pos - 1) {
                i++;
                continue;
            }
            // pos - 1 就是 pos 這個數正确的位置所在
            // 如果該位置已經有了 pos，那麼說明該數字重複了
            if (nums[pos - 1] == pos) {
                nums[i] = -1;
                i++;
                continue;
            }
            // 如果以上兩種情況都不符合
            // 那麼就需要交換數字，把這個數字換到正确的位置
            int tmp = nums[pos - 1];
            nums[pos - 1] = nums[i];
            nums[i] = tmp;
        }
        // 開始重新周遊數組，将 -1 設定為正确的數字
        List<Integer> list = new ArrayList<>();
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == -1) {
                list.add(j + 1);
            }
        }
        return list;
    }
}