题目:
一个 非严格递增排列 的数组 arr,原地删除重复出现的元素,使每个元素只出现一次 ,返回删除后数组的新长度。元素的相对顺序 应该保持 一致 。然后返回arr中唯一元素的个数。
分析:
1.确保数组内存在可比较的数字,即arr>0
2.有数字的前提下设置两个指针fast和slow,从arr[1]开始向后遍历
①当arr[fast] == arr[fast -1] 时,说明这两个元素是重复元素,后一个元素待覆盖,fast指针继续向 后寻找不重复元素
②当arr[fast] != arr[fast -1] 时,说明这两个元素不是重复元素,后一个元素需要向前移动到重复的元素位置上
在这种情况下我们用fast指针寻找不同的元素,用slow指针指向重复的待覆盖的元素,当fast指针越界时,slow指针指向的数组元素之前全部为未重复项
根据此原理即可解决本题
代码:
int remove_same(int* arr, int n)
{
if (n == 0 )
{
return 0;
}
int fast = 1, slow = 1;
while (fast < n)
{
if (arr[fast] != arr[fast - 1])
{
arr[slow] = arr[fast];
slow++;
}
fast++;
}
return slow;
}
int main()
{
int arr[] = {0, 0, 1, 1, 2, 2, 3, 3};
int length = sizeof(arr) / sizeof(arr[0]);
int n = remove_same(arr, length);
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
运行结果: