268.丢失的数字

跟41题类似
https://leetcode-cn.com/problems/missing-number/submissions/

R表示的是最好预期，我现在还没看过所有的数，最好的情况是啥样的，
——> 0~N-1我每个数字都收集到了1个，没有重复值
那么我缺失的数字就是R，也就是N

L要么不动，
只要L往右动了，那么L左侧都是i位置上面放的数是i

如果此时L位置来了个纯无用的数，比如负数，那么让L的数与R左边一个数交换，然后R来到N-1位置


所以此时包括R在内往右就都是垃圾区，R变成N-1说明我的最好预期在变差，
现在把最好预期调整为0~N-2我每个数字都收集到了1个，没有重复值，
那么我缺失的数字就是R, 也就是N-1

现在再来看L位置是无用的数有哪些情况？

• 
• 解释下第三种情况，
  • L来到4位置，发现值是17，既不小于L也不大于等于R， 那么就把它发货到它该去的位置，也就是17位置，但发现17位置已经躺了个17了，那么就相当于我收集到了2个17，我的最好预期在变差

    public int missingNumber(int[] arr) {
        //L左边都做到了i位置放的值是i
        int L = 0;
        int R = arr.length;
        while (L < R) {
            if (arr[L] == L) {
                L++;
            } else if (arr[L] < L || arr[L] >= R || arr[L] == arr[arr[L]]) {
                swap(arr, L, --R);
            } else {
                swap(arr, L, arr[L]);
            }
        }
        return L;
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }