給出一個整數(shù)數(shù)組母剥，范圍是1 ≤ a[i] ≤ n(n是數(shù)組的長度)滞诺，數(shù)組里有些元素出現(xiàn)了兩次形导，有些出現(xiàn)了一次，找出[1,n]的數(shù)組里沒有出現(xiàn)的數(shù)字习霹。要求是不能用額外的空間朵耕，時間復(fù)雜度為O(n)。
這里先說一下我的解法吧（很辣雞就是了hhhh）

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> result = new ArrayList<>();
    if (nums.length == 0) {
        return result;
    }
    Arrays.sort(nums);
    int last = nums.length;
    int index = 0, i;
    for (i = 1; i <= last && index < last;) {
        if (nums[index] == i) {
            index +=1;
            i += 1;
            continue;
        } else if (nums[index] < i) {
            index++;
            continue;
        } else {
            result.add(i);
            i++;
         }
      }
      for (; i <= last; i++) {
          result.add(i);
      }
      return result;
}

這里存在三種情況淋叶，缺的數(shù)在起始端阎曹、中間、末尾煞檩，而且存在重復(fù)的數(shù)字处嫌。我采用的方法是先對數(shù)組進(jìn)行排序，再從頭開始進(jìn)行對比斟湃。代碼我個人認(rèn)為還是比較好理解的熏迹。如果相同，進(jìn)行下一次對比凝赛，如果數(shù)組里的數(shù)小于i注暗，說明這個數(shù)是重復(fù)的，可以跳過墓猎。最后的一個for循環(huán)是處理類似[1,1,2,2]這樣缺的數(shù)在末尾的情況继蜡。其實我覺得Arrays.sort的復(fù)雜度應(yīng)該是O(nlgn)的顽频。悯蝉。骇陈。

辣雞代碼就看到這里，接下來看Top Solution里的幾種解法搀军。
第一種：

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> ret = new ArrayList<>();
    
    for (int i = 0; i < nums.length; i++) {
        int val = abs(nums[i]) - 1;
        if (val > 0) {
            nums[val] = -nums[val];
        }
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            ret.add(i+1);
        }
    }
}

這種解法的思路是：如果一個數(shù)組為[1,2,3....n]膨俐，那么通過一次迭代使nums[nums[i]-1] = -nums[nums[i]-1]之后，數(shù)組里的所有數(shù)都應(yīng)該為負(fù)值罩句，此時我們再進(jìn)行第二次迭代焚刺，若某個下標(biāo)對應(yīng)的值不為負(fù)數(shù)，那么該下標(biāo)+1的值就是缺少的值门烂。
再來看第二種：思路與上一種類似乳愉，這次是在第一次迭代時進(jìn)行nums[(nums[i]-1) % n] += n的操作，這樣一輪迭代之后屯远，如果某一個下標(biāo)對應(yīng)的值小于n蔓姚，那么該下標(biāo)+1的值就是缺少的值。
第三種方法是進(jìn)行交換：如果nums[i] != i + 1 && nums[i] != nums[nums[i]-1]就將nums[i]與nums[nums[i]-1]進(jìn)行交換慨丐，nums[i] != nums[nums[i]-1]這個條件是判斷這個數(shù)是否是重復(fù)的數(shù)字坡脐，最后再掃描一遍數(shù)組，如果下標(biāo)+1不等于nums[i]的值房揭，下標(biāo)+1就是缺少的那個數(shù)备闲，代碼如下

public List<Integer> findDisappearedNumbers(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
            int temp = nums[i];
            nums[i] = nums[temp - 1];
            nums[temp - 1] = temp;
        }
    }
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            res.add(i + 1);
    }
    return res;
}

拿示例數(shù)組[4, 3, 2, 7, 8, 2, 3, 1]來說吧晌端，作者給出了完整的運行過程，可以幫助理解

[4,3,2,7,8,2,3,1]
[7,3,2,4,8,2,3,1]
[3,3,2,4,8,2,7,1]
[2,3,3,4,8,2,7,1]
[3,2,3,4,8,2,7,1]
[3,2,3,4,1,2,7,8]
[1,2,3,4,3,2,7,8]

還有用Python一行搞定的恬砂。咧纠。不懂Python所以沒有看，有興趣可自行閱讀泻骤。