前言: 本文章是关于在力扣上面的数组相关面试题的讲解，包括: 1.原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1), 2.删除排序数组中的重复项。 3. 合并两个有序数组。
一.原地移除数组中所有的元素val
题目:
https://leetcode.cn/problems/remove-element/
1.1时间复杂度为O(N^2)，空间复杂度为O(1)
写一段原地移除数组中所有的元素val，要求时间复杂度为O(N^2)，空间复杂度为O(1)的代码实现:
思路:遇到这个val后面的元素往前面覆盖。
int removeElement(int* nums, int numsSize, int val) { int i, j; int newSize = numsSize; for (i = 0; i < newSize; i++) { if (nums[i] == val) { for (j = i; j < newSize - 1; j++) { nums[j] = nums[j + 1]; } newSize--; i--; // 重复检查当前位置 } } return newSize; }
int main() {
int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
int val = 2;
int newSize = removeElement(nums, numsSize, val); printf("修改后的数组: "); for (int i = 0; i < newSize; i++) { printf("%d ", nums[i]); } return 0; }
1.2时间复杂度为O(N)，空间复杂度为O(N)
写一段原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(N)的代码实现:
思路:
#include <stdlib.h> int* removeElements(int* nums, int numsSize, int val, int* newSize) { int i, j; int* tmp = (int*)malloc(numsSize * sizeof(int)); // 创建一个临时数组 int count = 0; // 计数器，记录移除元素后的数组长度 for (i = 0; i < numsSize; i++) { if (nums[i] != val) { tmp[count] = nums[i]; // 将非 val 元素保存到临时数组 count++; } } *newSize = count; // 更新新数组的长度 return tmp; // 返回临时数组的指针 } int main() { int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int val = 2; int newSize; int* newArray = removeElements(nums, numsSize, val, &newSize); printf("移除元素后的数组: "); for (int i = 0; i < newSize; i++) { printf("%d ", newArray[i]); } printf("\n新长度: %d\n", newSize); free(newArray); // 释放临时数组的内存 return 0; } ```
1.3符合此题的正确写法:
原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1):
写法2与这篇文章的唯一的区别是本文章需要return j，其余部分一样，而写法1的大致思路画图思路相差不大，就不用动图演示了,传送门–>序列中删除指定数字,有动图演示
图解:
#include<stdio.h> /写法一 int removeElement(int *nums,int numsSize,int val) { int src = 0; int dst = 0; while (src < numsSize) { if (nums[src] != val) { nums[dst++] = nums[src++]; } else { src++; } } return dst; } //写法二 int removeElement(int* nums, int numsSize, int val){ int i=0; int j=0; for(i=0;i<numsSize;i++) { if(nums[i]!=val) { nums[j++]=nums[i]; } } return j; }
int main() {
int nums[] = { 0, 1, 2, 2, 3, 0, 4, 2 };
int sz =sizeof(nums) / sizeof(nums[0]);
int val = 2;
int ret=removeElement(nums, sz, val);
printf(“%d”,ret);
}
二. 删除排序数组中的重复项。
题目:
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
动图演示:
#include<stdio.h> int removeDuplicates(int* nums, int numsSize) { int src = 1, dst = 0; while (src < numsSize) { if (nums[src] != nums[dst]) { nums[++dst] = nums[src++]; } else { src++; } } return dst+1;//因为dst是下标，所以要+1 } int main() { int nums[] = { 0,0,1,1,1,2,2,3,3,4 }; int sz = sizeof(nums) / sizeof(nums[0]); int ret=removeDuplicates(nums, sz); printf("%d", ret); }
执行：
三. 合并两个有序数组
题目:
https://leetcode.cn/problems/merge-sorted-array/
思路:无论是下面哪种情况，nums1数组都是目标数组，都是长的那个。
要是end2先结束，那就不用拷贝到目标数组nums1，直接打印nums1即可
若是end1先结束，需要先把nums2(短数组的元素)拷贝到nums1，再打印
3.1end1>0，end2<0
3.2end1<0,end2>0
代码实现:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int end1=m-1; int end2=n-1; int i=m+n-1; while(end1>= 0&& end2>=0) { if(nums1[end1]>nums2[end2]) { nums1[i--]=nums1[end1--]; } else { nums1[i--]=nums2[end2--]; } } while(end2>=0) { nums1[i--]=nums2[end2--]; } }
执行:
文章到这就写完了，如有错误欢迎指正，谢谢！
