数据结构（C语言篇）：（三）顺序表算法题解析

前言

上期博客中，博主为大家介绍了顺序表的相关基础知识，这期博客博主就来带大家做几道顺序表的相关算法题，来加深一下对顺序表的理解~下面就让我们正式开始吧！

一、移除元素

1.1 题目介绍

题目链接：https://leetcode.cn/problems/remove-element/description/

1.2 思路分析及代码实现

1.2.1 思路1：双指针（快慢指针）

双指针法是解决此类问题的通用方法，我们将使用两种指针：

• 慢指针（slow）：指向下一个可以放置非目标值的位置
• 快指针（fast）：遍历整个数组

算法步骤如下：

1. 首先初始化慢指针 slow = 0；

2. 然后使用快指针 fast 遍历数组，如果nums[fast] != val，将 nums[fast] 复制到 nums[slow] ，然后 slow++ ；

3. 遍历结束后，slow 代表的就是新数组的长度。

本算法的时间复杂度是

O(n)

，空间复杂度是

O(1)

代码实现如下：

int removeElement(int* nums, int numsSize, int val) {
    int slow = 0;
    for (int fast = 0; fast < numsSize; fast++) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

1.2.2 思路二：双指针优化（当要移除的元素很少时）

当要移除的元素很少时，方法一可能会做很多不必要的复制操作（特别是当目标值很少时）。

因此我们可以给出如下的算法步骤：

1. 初始化左指针 left = 0，右指针 right = len(nums) - 1

2. 当 left <= right 时：

如果nums[left] == val，将nums[left] 与 nums[right] 交换，然后 right-- ；

否则，left++。

3. 当循环结束时，left 就是所求新数组的长度。

这种方法时间复杂度也是

O(n)

，空间复杂度也是

O(1)

。

代码实现如下：

int removeElement(int* nums, int numsSize, int val) {
    int left = 0;
    int right = numsSize - 1;
    
    while (left <= right) {
        if (nums[left] == val) {
            // 将右指针的元素复制到左指针位置
            nums[left] = nums[right];
            right--;
        } else {
            left++;
        }
    }
    
    return left;
}

二、删除有序数组中的重复项

2.1 题目介绍

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

下面我们同样给出两种思路：

2.2 思路分析及代码实现

2.2.1 思路一：遍历数组

我们可以创建一个新数组，然后遍历原数组，将不重复的数据导入到原数组之中，再将新数组中的数据导入到原数组中。

由于本方法的复杂度情况较差，故此处不再多赘述，直接介绍第二种思路。

2.2.2 思路二：双指针（快慢指针）

由于数组是有序的，重复的元素一定会相邻出现，我们依旧可以使用双指针方法。

算法步骤如下：

1. 初始化慢指针 slow = 1（因为第一个元素肯定是不重复的）
2. 使用快指针 fast 从索引 1 开始遍历数组：
   • 如果 nums[fast] != nums[fast - 1]，说明找到了新的不重复元素
   • 将 nums[fast] 复制到 nums[slow]，然后 slow++
3. 遍历结束后，slow 就是新数组的长度

本方法的时间复杂度：

O(n)

，空间复杂度：

O(1)

代码实现如下：

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    int slow = 1;
    for (int fast = 1; fast < numsSize; fast++) {
        if (nums[fast] != nums[fast - 1]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    return slow;
}

三、合并两个有序数组

3.1 题目介绍

题目链接：https://leetcode.cn/problems/merge-sorted-array/description/

3.2 思路分析及代码实现

3.2.1 思路：逆向双指针

由于nums1的后半部分是空的，我们就可以从后向前填充，这样可以避免覆盖 nums1 中尚未处理的元素。

算法步骤如下：

1. 初始化三个指针：

• p1：指向 nums1 的有效元素末尾（索引 m-1）
• p2：指向 nums2 的末尾（索引 n-1）
• p：指向 nums1 的最终位置末尾（索引 m+n-1）

2. 从后向前遍历：

• 比较 nums1[p1] 和 nums2[p2]，将较大的元素放到 nums1[p]
• 相应的指针向前移动

3. 如果 nums2 还有剩余元素，直接复制到 nums1 的前面

本算法的时间复杂度：

O(n)

，空间复杂度：

O(1)

代码实现如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int p1 = m - 1;      // nums1有效元素的末尾
    int p2 = n - 1;      // nums2的末尾
    int p = m + n - 1;   // 合并后的末尾
    
    // 从后向前合并
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
    
    // 如果nums2还有剩余元素，直接复制
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
}

总结

以上就是本期顺序表OJ题的解析了，下期博客将更新链表的相关知识，请大家多多支持！