给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
使用双指针法, 可以将时间负责度o(n^2)的解法优化为o(n)。
这个算法只需要遍历一次就可以得到对应数组的长度
图解 : (官方教程)
int[] a = new[] {1, 1, 1, 2, 3, 4};
public void OutPutArrayLength(int[] a)
{
int q = 0;
int p = q + 1;
int index = 0;
for (int i = 0; i < a.Length - 1; i++)
{
q = i;
p = q + 1;
if (a[q] != a[p])
{
index++;
int tmp = a[p];
a[p] = a[index];
a[index] = tmp;
}
}
}
return index+1;