删除有序数组里的重复元素

tech2022-10-06  104

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 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;
最新回复(0)