顺序表算法题(双指针法)
移除元素
题目链接:LeetCode - 移除元素
这道题是双指针法的经典入门。思路很简单:创建两个变量 src 和 dst,src 负责探路,寻找非目标值的元素;dst 负责站岗,记录有效数据的位置。
当 src 指向的数据不等于 val 时,将其赋值给 dst 位置,然后 dst 前进一步;无论是否赋值,src 都要前进一步。最终 dst 的值即为新数组的长度。
时间复杂度:O(N)
空间复杂度:O(1)
// 移除元素
int removeElement(int* nums, int numsSize, int val){
// 创建两个变量
int src = 0, dst = 0;
while(src < numsSize){
// src 指向的数据不是 val,赋值并移动 dst
if(nums[src] != val){
nums[dst] = nums[src];
dst++;
}
src++;
}
return dst;
}
删除有序数组中的重复项
同样是双指针法,但这里利用了数组有序的特性。src 指向当前检查的元素,dst 指向已去重部分的末尾。
如果 src 和 dst 指向的值不同,说明遇到了新元素,将 dst 后移并赋值;如果相同则跳过。注意优化点:如果 ++dst == src,意味着自己给自己赋值,可以跳过。
时间复杂度:O(N)
空间复杂度:O(1)
// 删除有序数组中的重复项
int removeDuplicates(int* nums, int numsSize){
// 创建两个变量,分别指向数组起始和下一个位置
src = , dst = ;
(src < numsSize){
(nums[src] != nums[dst] && ++dst != src){
nums[dst] = nums[src];
}
src++;
}
dst + ;
}


