https://leetcode-cn.com/problems/first-missing-positive/

这道题coding感很强，典型的代码比思路少的

整体流程图

过流程

• L的含义：
  • 0到L- 1这个范围的每个位置都做到了i位置放的数是i + 1

• R的含义：

  • ① 我没有看过的数，假设凑的时候以最优预期来看，缺失的最小正整数最大能是多少，比如上图就是，R左边能不能把1~10攒齐（并且是以连续地来攒）？若能，那么11就是缺失的最小正整数。(R的含义是以R+1为基础的 )
    • 一句话就是：最好预期下尽可能大的缺失的最小正整数

• 明白了两个含义后，接下来开始走流程

  • 
  • 一开始来了个-7，不是1~10内的，不是我我们要的，让-7和R左边一个数（？）交换，然后R往左移动一个位置
  • 
    • 我们最好预期在变差，因为来了个-7，现在0~9位置的范围内我们的预期是数字1~9了，

  • 假设 ？ 是15

    • 

    • 现在我们的预期是攒齐数字1-9，15不是我们的预期，所以让它跟R左边一个位置（？）交换， R来到8位置

                攒齐数字1~9已经没指望了， 预期在变差，现在是预期攒齐1~8

  • 

    • 假设？是9， 不是我们需要的，
  • 
  • 
  • 最好预期继续在变差，现在的预期是攒齐数字1~7

• 总结一下什么是不需要的数1：当最好预期是1~R时，若出现了个数>R, 那么它就是我门不要的数，最小预期在变差

接下来看另一种情况，（现在预期是攒齐数字1~7）

假设现在L位置来了个1，让L往右移动， （L的含义是让0到L-1位置范围内的数做到i位置放的值是i + 1, 现在0位置放的数是1，做到了，所以让L往右移动一格）

• 快进一下
  • 
    • 现在3位置来了个1，是我们需要的吗？我们不需要了，因为我们现在已经攒齐了连续的123，你来个1干嘛？原来我的最好预期是攒齐数字1~7，你现在来了个1，我只能攒齐1~6了（预期在变差）
  • 预期1~6

    总结一下这种情况什么是不需要的数？ 当前数字小于等于L位置左边一个数，（也就是<=L, 因为左边一个位置的数正好的L的下标嘛） 那它就是我们不需要的

• 接下来看这种情况

假设现在3位置来个数字5， 4位置和5位置的数还不知道， 那么按道理数字5应该放在4位置上，然后把4位置上的问号拿到3位置重复看， 但如果你发现4位置上已经躺了一个5了，那么3位置的5就是不需要的，

总结一下这种情况什么是不需要的数？ L位置上的数字V应该是放在 V-1位置上的，但V - 1位置上已经有数字V了， 那么L位置上的数字V就是不需要的数

接下来让3位置的数字5和？交换，然后R往左动

就这样一直下去，L和R一定能相遇，相遇的时候你就知道你缺谁了

再过一个例子，理顺一下

两个含义：

三个逻辑：

4）

开始过例子

来了个数字6，它应该去5位置，并且发现5位置？不是6，那么就把6和这个？交换， 然后重复地回到L位置来看这个？

coding中的最后一个else是这种，两个数不相等

代码

      public int firstMissingPositive(int[] arr) {
        //L含义: arr[0.....L-1]这个范围的每个位置都做到了i位置放的数是i+1
        int L = 0;
        //R含义: R左边能不能把数字1~R攒齐？（并且是连续地攒），若能，那么R + 1就是缺失的最小正整数
        int R = arr.length;
        while (L < R) { // L和R相遇就退出
            if (arr[L] == L + 1) { // i位置放的数是 i + 1, 那么就是我们要的数
                L++;
            } else if (arr[L] <= L || arr[L] > R || arr[L] == arr[arr[L] - 1]) {
                //条件arr[L] <= L:  arr[L] 小于等于它左边的一个数（也就是L）
                //条件arr[L] > R:
                //条件arr[L] == arr[arr[L] - 1]: arr[L]的数应该放在下标为arr[L] - 1的位置上，若这个位置已经有放了跟arr[L]值一样的数，那么就不需要这个arr[L]了
                swap(arr, L, --R);
            } else { //  arr[L] != arr[arr[L] - 1]
                swap(arr, L, arr[L] - 1);
            }
        }
        return R + 1;
    }
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }