765. Couples Holding Hands

题目
https://leetcode-cn.com/problems/couples-holding-hands/description/
思路:
排成一列，两两一对。那么最后的情况必然是2，2，2，2分隔，也即row[2n],row[2n+1]位置是一对。
对于row[0]来说，如果row[1] 和 row[0]是夫妻，那么他们两个就都不动就好。如果两个都移走，那么不是最优。
考虑row[0]和row[1]不是夫妻的情况
操作1: 要么把row[0]和 row[0]的夫妻边上的交换
操作2: 要么把row[1]和row[0]的夫妻交换
操作3：要么row[0]和row[1]都移走。
显然操作3要不得。

而操作1和操作2等价。我们为了遍历方便（每次后移两个），采取操作2
如果每次都去寻找row[i]的夫妻的位置，可能需要n-i-1次遍历。一共n/2次寻找。复杂度O(n^2)，所以这里优化一下，我们用一个position数组，记录对应值所在的位置。如 0 2 3 1的position数组为[0,3,1,2]。即position[row[i]]=i;

特别注意，交换的时候除了交换row，也要交换position。而且position交换在前（如果提前缓存了row[i+1]的值则不用提前），这是因为交换row后，row[i+1]的值也变了

class Solution {
    public int minSwapsCouples(int[] row) {
        int[] position = new int[row.length];
        int count=0;
        for(int i=0;i<row.length;i++){
            position[row[i]]=i;
        }
        for(int i=0;i<row.length;i=i+2){
            //邻座即情侣，无需交换
            if(row[i]/2==row[i+1]/2){
                continue;
            }else{
                //找到对应情侣的位置，换到i+1处
                int m=(row[i]%2==0)?(row[i]+1):(row[i]-1);
                int index = position[m];
                swap(position,row[i+1],m);
                swap(row,i+1,index);
                count++;
            }
        }
        return count;
        
    }
    private void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}

41. First Missing Positive

题目
https://leetcode-cn.com/problems/first-missing-positive/description/
思路
其解题核心思想是将数组的第i位存正数i+1。最后再遍历一次就可以。
1.一开始想的是，对于长度为n的nums，只需要开辟一个长度为n辅助数组，位置i对应数字i。遍历nums,然后给辅助数组赋值，比如遍历到5,就有temp[4]=1。然后遍历辅助数组，找到第一个非正数的位置，它代表的就是缺少的第一个正数
2.但是题目要求常数辅助空间，考虑把原数组本身当做辅助数组，通过swap的方式来进行，使得数组如果存在对应正数，则对应位置的数字为正数。于是有了解法1:如果是当前位置对应的数字为非正数或者当前位置就是应该存在的位置，则不进行交换；如果当前位置对应的数字大于数组范围（也即数组中不存在可以交换的位置），或者是交换位置的数字正好是重复的（如果直接交换可能死循环），则把当前位置置负；否则，交换当前位置和理想位置的数字，然后继续对当前位置的值做交换和判断。
数组的每个位置在交换时只会访问一次（直接过滤的不算在内），时间复杂度O(cn)

class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i=0;i<nums.length;i++){
            findAndSwap(nums,i);
        }
        int result=nums.length+1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]<=0){
                result=i+1;
                break;
            }
        }
        return result;
    }
    public void findAndSwap(int[] nums,int position){
        int swapNum = nums[position];
        if(swapNum<=0 || position==swapNum-1)return;
        else if(swapNum>nums.length||swapNum==nums[swapNum-1]){
            nums[position]=-1;
        }else{
            swap(nums,position,swapNum-1);
            findAndSwap(nums,position);
        }
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }    
}

3.进一步考虑一下呢？如果我们能够保证对于出现的范围内的正数nums[i]==i+1，那么首先不满足这个等式的正数，就是缺失的正数。
边界值：非正数/大于范围的正数/要交换的两数相等。除了边界情况，都和理想位置上的数字进行交换。

image.png

class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i=0;i<nums.length;i++){
            while(nums[i]>0&&nums[i]<=nums.length&&nums[i]!=nums[nums[i]-1]){
                swap(nums,i,nums[i]-1);
            }
        }
        int result=nums.length+1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=i+1){
                result=i+1;
                break;
            }
        }
        return result;
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

类似题目
n个元素的数组，里面的数都是0~n-1范围内的，求数组中反复的某一个元素。没有返回-1, 要求时间性能O(n) 空间性能O(1)。

leetcode——hard

leetcode——hard

765. Couples Holding Hands

41. First Missing Positive