C语言算法-解答删除有序数组中的重复项问题的C语言实现

题目

给定一个有序数组 nums，删除重复的元素，使得每个元素只出现一次，并返回新数组的长度。

引言

删除有序数组中的重复项问题需要考虑数组的元素比较和移动的逻辑。我们可以使用双指针的方法来解决这个问题，一个指针用于遍历数组，一个指针用于记录新数组的位置。解决这个问题需要对数组进行元素比较和移动。

算法思路

我们将使用双指针的方法来解决删除有序数组中的重复项问题。

算法的步骤如下：

1. 如果数组的长度小于等于 1，则无需进行删除操作，直接返回数组的长度。
2. 定义两个指针 slow 和 fast，初始时都指向数组的第一个元素。

3. 迭代遍历数组，从第二个元素开始：

   • 如果 fast 指向的元素与 slow 指向的元素相等，说明出现了重复项，继续向后遍历。
   • 如果 fast 指向的元素与 slow 指向的元素不相等，将 fast 指向的元素复制到 slow + 1 的位置，然后将 slow 向后移动一位。
4. 返回 slow + 1，即新数组的长度。

代码实现

下面是使用C语言实现的代码：

#include <stdio.h>

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize <= 1) {
        return numsSize;
    }

    int slow = 0;
    int fast = 1;

    while (fast < numsSize) {
        if (nums[fast] != nums[slow]) {
            nums[slow + 1] = nums[fast];
            slow++;
        }
        fast++;
    }

    return slow + 1;
}

int main() {
    int nums[] = {1, 1, 2, 2, 3, 4, 4, 5};
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    printf("Original Array: ");
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    int newLength = removeDuplicates(nums, numsSize);

    printf("New Array: ");
    for (int i = 0; i < newLength; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    return 0;
}

算法分析

该算法只需要对数组进行一次遍历，并在元素比较不相等时进行元素复制，所以时间复杂度为 O(n)，其中 n 是数组的长度。

空间复杂度为 O(1)，算法只使用了常数级别的额外空间。

示例和测试

示例输入:

Original Array: 1 1 2 2 3 4 4 5

示例输出:

New Array: 1 2 3 4 5

总结

本文使用C语言实现了解答删除有序数组中的重复项问题的代码。通过使用双指针的方法，我们能够删除数组中的重复元素，使得每个元素只出现一次，并返回新数组的长度。该算法的时间复杂度为 O(n)，空间复杂度为 O(1)。