数据结构刷题数组oj
前言:
本文章是关于在力扣上面的数组相关面试题的讲解,包括:
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--];
}
}
执行:
文章到这就写完了,如有错误欢迎指正,谢谢!
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfaibh
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01