介绍几道LC上双指针排序的问题

面试题21题

• index指向的是奇数的最后一个位置，那么index+1指向的是偶数的第一个位置
• 假设现在的序列是 1 3 2 4 5，那么index指向的是3，i指向的是5。所以现在要将2和5来交换
• 先将index的下标加1，再和5交换

 void swap(int nums[],int i,int j)
    {
        if(i==j) return;
        nums[i]=nums[i]^nums[j];
        nums[j]=nums[i]^nums[j];
        nums[i]=nums[i]^nums[j];
    }

    public int[] exchange(int[] nums) {
        int index=-1;
        for(int i=0;i<nums.length;i++)
            if(nums[i]%2==1) swap(nums,i,++index);
        return nums;
    }

LC 283

• index是第一个不为0的数字，剩下的和上面的一样

 void swap(int arr[],int i,int j)
    {
        if(i==j) return;
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }

    public void moveZeroes(int[] nums) {
        int index=-1;
        for(int i=0;i<nums.length;i++)
            if(nums[i]!=0) swap(nums,++index,i);
    }

LC75

• l指向0的最后一个,所以要将初始值设置为-1，当cur=0时，先将l加一再交换和cur的值。由于交换过来的值必然是1，所以将cur++
• r指向的是2的最前面一个值，所以初始值设置为nums.length，当cur=2时，先将r减一再交换
• 由于r指向的是2最前面的元素，所以小于r就可以终止了

void swap(int nums[],int i,int j)
    {
        if(i==j) return;
        nums[i]=nums[i]^nums[j];
        nums[j]=nums[i]^nums[j];
        nums[i]=nums[i]^nums[j];
    }

 public void sortColors(int[] nums) {
     int cur=0,r=nums.length,l=-1;
     while(cur<r){
         if(nums[cur]==0) swap(nums,++l,cur++);
         else if(nums[cur]==1) cur++;
         else swap(nums,cur,--r);
     }
  }