前提:
双指针算法去重有一个前提,那就是数组已经是有序的状态。若数组并非有序,可以在使用本次算法之前先使用排序算法将数组转换成有序数组。本次算法为原地算法即额外空间复杂度为O(1)。本文将使用整数型数组arr作演示,其中arr的元素为0,0,1,2,2,3,5。
算法讲解:
首先我们设置一个记录要被替换位置的指针left,再设置一个游走指针right。
让right指针遍历整个数组,当right指针到达数组最后一个数字时为算法结束的标志。每一次遍历时判断left指针所指元素的值与right所指是否相等。相等代表数组存在相等的数,这时考虑到right后一位的值可能也与left值相等,即arr[left]=arr[right]=arr[right+1] 的情况,因此需要继续后移right指针,直到right所指值与left不同。
当right所指值与left不同时意味着left指针所指值重复结束。这时保留left的位置,将left后移一位后将right的值赋值给left,同时将right后移一位。
重复该操作知道right指针抵达数组的最后一个元素,在数组前left位置可以得到该数组的有序无重复数组。如本文的例子完成算法后结果为: 0, 1, 2, 3, 5, 3, 5,此时的left为4。
算法代码:
public int removeDuplicates(int[] arr) {
int left = 0; //左边指针
int right = 1; //右边指针
while (right < arr.length) {
// 当左指针所指值与右指针所指值相等时,右指针后移
if (arr[left] == arr[right]) {
right++;
} else {
/*当左指针所指与右指针不同时,左指针后移后将右指针所指值赋值给左指针,
再将右指针右移一位*/
arr[++left] = arr[right++];
}
}
return left + 1;
}
在方法的最后我返回了一个值left+1,即数组中不重复的数。
————————————————