顺序表oj习题

一. leetcode 27 移除元素

https://leetcode.cn/problems/remove-element/description/

int removeElement(int* nums, int numsSize, int val) {
    //双指针法（从功能上看，它们承担了 “指向” 数据位置的角色，因此习惯上被称为 “指针”（更准确地说，是 “索引指针” 或 “伪指针”））
    //如果src指向的数据是val,则src++
    //如果src指向的数据不是val，则dst和src都++
    int dst=0;
    int src=0;
    while(src<numsSize)
    {
        if(nums[src]!=val)
        {
            nums[dst]=nums[src];
            dst++;
        }
        src++;
    }
    return dst;
}

思路

双指针法，通过两个指针（src 与 dst）原地修改数组，高效移除目标值。

src（源指针）：遍历整个数组，寻找非目标值元素。

dst（目标指针）：指向待填充位置，记录有效元素的个数。

解题过程

初始化 src 和 dst 均为 0。

当 src 未遍历完数组时：

若 nums[src] 不是目标值 val，则将其复制到 nums[dst]，并移动 dst 到下一个位置。

无论是否为目标值，src 均向前移动一步。

遍历结束后，dst 的值即为有效元素的个数，返回 dst。

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(1)

二. leetcode 26 删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

int removeDuplicates(int* nums, int numsSize) {
    int dst=0;
    int src=0;
    while(src<numsSize)
    {
        if(nums[src]!=nums[dst] && src!=dst++)
        {
            nums[dst]=nums[src];
        }
        src++;
    }
    return dst+1;
}

思路

双指针法，通过两个指针（dst 和 src）修改

src（源指针）：从下标为1的元素开始遍历整个数组，寻找与dst指向不同的元素

dst（目标指针）：指向已去重区域的最后一个元素，标记下一个待填充区域

解题过程

初始化 src=1（跳过首个元素）、dst=0。

当 src 未遍历完数组时：

若 nums[src] 与 nums[dst] 不同，且 src 与 dst+1 不重合（避免无意义赋值），则将 nums[src] 复制到 nums[dst+1]，同时 dst 后移一位。

src 始终向前移动一步。

遍历结束后，dst+1 即为去重后数组的长度，返回该值。

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(1)

三. 合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/description/

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1=m-1;
    int l2=n-1;
    int l3=m+n-1;
    while(l1>=0 && l2>=0)
    {
        if(nums1[l1]>nums2[l2])
    {
        nums1[l3--]=nums1[l1--];
    }
    else
    {
        nums1[l3--]=nums2[l2--];
    }
    }
    while(l2>=0)
    {
        nums1[l3--]=nums2[l2--];
    }

}

思路

逆向双指针法，利用 nums1 尾部空闲空间，从后向前合并，避免覆盖未处理元素。

l1：指向nums1有效元素的末尾(m-1)

l2：指向nums2有效元素的末尾(n-1)

l3：指向合并后的数组末尾(m+n-1)

解题过程

1.初始化三个指针分别对应的位置；

2.当l1和l2为越界时： 比较两指针指向的元素大小，将较大值放在l3位置， 对应指针和l3均向前移动一步；

3.若nums1仍有剩余元素，则不用管， 若nums2仍有剩余元素（l2>=0），依次放入nums1剩余位置。

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(1)

小结：

顺序表作为数据结构的入门基础，其思维模式会贯穿后续链表、栈、队列等更复杂结构的学习。建议大家课后再动手复现一遍解题过程，遇到疑问时对照代码逐行调试，真正把 “看懂” 变成 “会写”。​

如果大家在练习中发现新的解题角度，或是有没搞懂的知识点，欢迎在评论区留言讨论。后续我也会持续更新数据结构相关的 OJ 解析，咱们一起在刷题中夯实基础，稳步进阶！​