Leetcode经典题目之“双指针交换元素“类题目

1 LC 27. 移除元素

class Solution {public int removeElement(int[] nums, int val) {int n=nums.length;int s=0;for(int i=0;i<n;i++){// 只有不等于目标值的时候才会进行交换，然后移动s指针if(nums[i]!=val){swap(nums,i,s++);}}return s;}void swap(int[]nums, int i, int j){int t=nums[i];nums[i]=nums[j];nums[j]=t;}
}

2 LC 删除有序数组中的重复项

class Solution {public int removeDuplicates(int[] nums) {int n=nums.length;int s=0;for(int i=1;i<n;i++){// 这个if条件也可以换成if(nums[i-1]!=nums[i])， 但是写成下面这样更方便理解，// 因为if(nums[s]!=nums[i]){nums[++s]=nums[i];}}return ++s;}
}

3 LC80. 删除有序数组中的重复项 II

参考解析：双指针解法

    public int removeDuplicates(int[] nums) {int n=nums.length;if(n<2){return n;}int s=2,f=2;while(f<n){if(nums[s-2]!=nums[f]){nums[s++]=nums[f];}f++;}return s;}

4 LC912. 快速排序数组：涉及到划分区间的问题，比如将小于等于目标值的元素都移动到左边，大于目标值的元素都移动到右边。参考下面的partition方法

  public int[] sortArray(int[] nums) {quickSort3(nums,0,nums.length-1);return nums;}void quickSort3(int[]arr,int i, int j) {if(i>=j)return;int pivot=partition(arr,i,j);quickSort3(arr,i,pivot-1);quickSort3(arr,pivot+1,j);}int partition(int[]arr,int l, int r){Random rand=new Random();int pivot = rand.nextInt(r-l+1)+l;swap(arr,pivot,r);int i=l-1;for(int j=l;j<r;j++){// 符合条件的才进行移动，对指针if(arr[j]<=arr[r]){swap(arr,++i,j);}}swap(arr,r,++i);return i;}void quickSort(int[]arr,int i, int j) {if(i>=j){return;}int base=arr[i];int p=i,q=j;for(int k=i+1;k<=q;){if(arr[k]<base){swap(arr,k,p);p++;k++;}else if(arr[k]>base){swap(arr,k,q);q--;}else{k++;}}for(int k=i;k<=j;k++){System.out.print("k:"+k+","+arr[k]+" ");}quickSort(arr,i,p-1);quickSort(arr,q+1,j);}