当前位置：首页 > news >正文

数据结构C语言练习(顺序表)

news 2025/4/2 6:05:32

本篇的题目：

1.移除元素

2.删除排序数组中的重复项

3.合并两个有序数组

可点击上面链接先做

1.移除元素

思路：

方法1：暴力移除（双循环移动元素）

1. 从前往后遍历nums，找到val第一次出现的位置
2. 将val之后的所有元素整体往前搬移，即删除该val
3. nums中有效元素个数减少一个循环进行上述操作，直到nums中所有值为val的元素全部删除完
时间复杂度:O(N^2) 空间复杂度:O(1)

方法2：临时数组辅助

1. 创建一个长度与nums相同的数组temp
2. 遍历nums，将nums中所有与val不同的元素搬移到temp中
3. 将temp中所有元素拷贝回nums中
时间复杂度: O(N) 空间复杂度: O(N)

方法3：双指针法（快慢指针）

1.初始化快慢指针，slow 和 fast 都从 0 开始。
2.快指针遍历数组，当遇到非 val 元素时，将其赋值给 slow 位置，slow 后移。
3.遍历结束，slow 的值就是有效元素个数。
时间复杂度 O(N) 空间复杂度: O(1)

方法1：暴力移除（双循环移动元素）

int removeElement1(int* nums, int numsSize, int val) {int k = numsSize;for (int i = 0; i < k; ) {if (nums[i] == val) {// 后续元素前移for (int j = i; j < k - 1; j++) {nums[j] = nums[j + 1];}k--; // 有效元素数量减 1} else {i++;}}return k;
}

方法 2：临时数组辅助

int removeElement2(int* nums, int numsSize, int val) {int* temp = (int*)malloc(numsSize * sizeof(int));int idx = 0;// 筛选非 val 元素到 tempfor (int i = 0; i < numsSize; i++) {if (nums[i] != val) {temp[idx++] = nums[i];}}// 拷贝回原数组for (int i = 0; i < idx; i++) {nums[i] = temp[i];}free(temp); // 释放临时数组内存return idx;
}

方法 3：双指针法（快慢指针）

int removeElement3(int* nums, int numsSize, int val) {int slow = 0; // 记录有效元素位置for (int fast = 0; fast < numsSize; fast++) {if (nums[fast] != val) {nums[slow] = nums[fast]; // 非 val 元素覆盖到 slow 位置slow++; // slow 后移}}return slow; // 返回有效元素数量
}

2.删除有序数组中的重复项

思路：

方法1：计数法

1. 设置一个计数，记录从前往后遍历时遇到的不同元素的个数由于不同的元素需要往前搬移，那count-1就是前面不同元素搬移之后，最后一个元素的位置，下一次在遇到不同元素就应该搬移到count位置。
2. 遍历数组，如果nums[i]与nums[count-1]不等，就将nums[i]搬移
到nums[count]位置，不同元素多了一个，给count++
3. 循环结束后，返回count

时间复杂度：O(N) 空间复杂度：O(1)。

方法2：双指针（快慢指针）
1.处理空数组。如果数组长度 0，直接返回 0。
2.初始化快慢指针。slow 指向第一个元素，fast 从第二个开始。因为有序，只要 fast 遇到和 slow 不同的，就是新元素。
3.遍历数组。fast 逐个检查，发现不同时，slow 后移，把 fast 的元素复制到 slow 位置。这样 slow 及之前都是唯一元素。
4.最后 slow+1 就是数量，因为初始 slow=0，处理后数量是 slow+1。

时间复杂度 O(N) 空间复杂度 O(1)

方法 1：计数法

int removeDuplicates1(int* nums, int numsSize) {if (numsSize == 0) {return 0; // 处理空数组}int count = 1; // 至少有一个元素（数组非空）for (int i = 1; i < numsSize; i++) {if (nums[i] != nums[count - 1]) {nums[count] = nums[i]; // 搬移新元素count++; // 计数增加}}return count;
}

方法 2：双指针法（快慢指针）

int removeDuplicates2(int* nums, int numsSize) {if (numsSize == 0) {return 0; // 处理空数组}int slow = 0; // 慢指针指向唯一元素末尾for (int fast = 1; fast < numsSize; fast++) {if (nums[fast] != nums[slow]) { // 发现新元素slow++; // 慢指针后移nums[slow] = nums[fast]; // 复制新元素到慢指针位置}}return slow + 1; // 唯一元素数量
}

3.合并两个有序数组

思路：

方法1：双指针法（从后往前合并，原地修改）

1.大概思路创建3个变量，一个变量是第一个数组的有效数据的最后一个元素，第二个变量是容量最大的最后元素位置，第三个是第二个数组有效元素的最后一个，
2.利用容量最大的数组末尾的空闲空间，从后往前比较（前 m 个元素）和另一个数组的元素，将较大的元素放入容量最大的数组末尾，逐步向前合并。

时间复杂度：O(m+n)空间复杂度：O(1)

方法 2：临时数组 + 排序（低效方法）

1.先将 nums1 前 m 个元素和 nums2 合并到临时数组，再排序后复制回 nums1。

时间复杂度：O((m+n)log(m+n)) 空间复杂度：O(m+n)

方法 1：双指针法（从后往前合并，原地修改）

void merge(int* nums1, int m, int* nums2, int n) {int p1 = m - 1, p2 = n - 1, tail = m + n - 1;while (p1 >= 0 && p2 >= 0) {if (nums1[p1] > nums2[p2]) {nums1[tail--] = nums1[p1--];} else {nums1[tail--] = nums2[p2--];}}// 处理剩余元素（若 nums2 还有剩余）while (p2 >= 0) {nums1[tail--] = nums2[p2--];}// nums1 剩余元素无需处理，已在正确位置
}

方法 2：临时数组 + 排序（低效方法）

void merge(int* nums1, int m, int* nums2, int n) {int* temp = (int*)malloc((m + n) * sizeof(int));int i = 0, j = 0, k = 0;// 合并到临时数组while (i < m && j < n) {temp[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];}while (i < m) temp[k++] = nums1[i++];while (j < n) temp[k++] = nums2[j++];// 复制回 nums1for (i = 0; i < m + n; i++) {nums1[i] = temp[i];}free(temp);
}

总结：

双指针法在以下场景中广泛应用：

1. 数组元素的移除与筛选

场景：需 “原地” 移除数组中特定元素，或保留符合条件的元素。
示例：
- 移除元素（如 LeetCode 27 题）：快指针遍历数组，慢指针记录有效元素位置，将非目标值元素前移。
- 删除有序数组中的重复项（如 LeetCode 26 题）：利用数组有序性，快指针寻找新元素，慢指针维护唯一元素序列。