【LeetCode刷题指南】--数组串联,合并两个有序数组,删除有序数组中的重复项

发布于:2025-07-18 ⋅ 阅读:(12) ⋅ 点赞:(0)

🔥个人主页:@草莓熊Lotso

🎬作者简介:C++研发方向学习者

📖个人专栏: 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言:生活是默默的坚持,毅力是永久的享受。  

前言:随着编程相关知识点的学习,我们LeetCode的刷题也不能落下。在前面我们也接触到了洛谷和牛客这两个刷题网站,但是博主一直都在推荐大家使用力扣,是因为力扣的判题严谨且大部分都是接口型题目,与面试中的笔试题也更加贴合。那么还是老样子,博主会为大家提供我自己的思路和代码,但是算法题的解法肯定不止一个,欢迎大家一起交流和讨论。


目录

1.数组串联

2.合并两个有序数组

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


1.数组串联

题目链接: 1929. 数组串联 - 力扣(LeetCode)

题目描述: 

题目示例:

 思路:利用malloc开辟空间

解题过程:

1.先定义一个新数组,为它开辟空间,空间大小由题目可知申请为2*numsSize *sizeof(int);

2.我们先将原来数组中的元素放到新数组里,与此同时将原来数组中的元素再依次放入新数组变长后的部分 从下标i+numsSize开始。

具体解题过程图示如下:

复杂度:

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

代码演示: 

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getConcatenation(int* nums, int numsSize, int* returnSize) {
    int*ans=(int*)malloc(sizeof(int)*numsSize*2);
    for(int i=0;i<numsSize;i++)
    {
        ans[i]=nums[i];
        ans[i+numsSize]=nums[i];
    }
    *returnSize=2*numsSize;
    return ans;
}

2.合并两个有序数组

题目链接: 88. 合并两个有序数组 - 力扣(LeetCode)

题目描述:

题目示例:

 思路:双指针倒序原地合并

解题过程:

1.指针初始化,i指向num1前m个有效元素的末尾,j指向num2所有元素的末尾,k指向nums1合并后数组的末尾

2.从两个有序数组的末尾开始比较元素,将较大的元素先放入结果数组的末尾,结果数组其实就是合并后的num1

3.我们需要考虑到如果num1有效和num2中有一个提前结束了的情况

  • 如果是num1有效先结束,我们只需要把num2中剩下的元素直接继续放到结果数组中就行了
  • 如果是num2先结束,直接不用管了,nums1中参与合并的剩下的元素直接就放前面去了

具体解题过程图示如下:
 
复杂度: 

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

代码演示: 

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int i=m-1;
    int j=n-1;
    int k=m+n-1;
    while(i>=0&&j>=0)
    {
        if(nums1[i]>nums2[j])
        {
            nums1[k--]=nums1[i--];
        }
        else
        {
            nums1[k--]=nums2[j--];
        }
    }
    //如果nums2先结束,不用讨论nums1中剩下的放前面就行了

    while(j>=0)
    {
        nums1[k--]=nums2[j--];
    }
}

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

题目链接:26. 删除有序数组中的重复项 - 力扣(LeetCode)

题目描述: 

题目示例: 

思路: 双指针

解题过程:

1.先抽象定义两个指针,实际上就是变量,dst=0,src=dst+1;

2.利用这两个指针,如果src的值等于dst的值,直接src++;如果src的值不等于dst的值,就先++dst再赋值,最后src++。这里需要注意一下当src与++dst指向同一个位置的时候就不需要赋值了,所有可以用&&把两个条件写在一起。

3.最后这里利用k记录下dst+1的值,也就是题目所需要的答案,直接返回就行了

具体解题过程图示如下: 

复杂度: 

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

代码演示: 

int removeDuplicates(int* nums, int numsSize) {
    int dst=0;
    int src=dst+1;
    while(src<numsSize)
    {
        //当src的值等于dst的值时,src++
        //当src的值不等于dst的值时,先dst++,再赋值,src++
        if(nums[src]!=nums[dst]&&++dst!=src)
        {
            nums[dst]=nums[src];
        }
        src++;
    }
    int k=dst+1;
    return k;
}


往期回顾: 

【数据结构初阶】--单链表(一)

【数据结构初阶】--单链表(二)

【LeetCode刷题指南特别篇】--移除链表元素,调试技巧,链表分割

结语:本篇文章就到此结束了,《LetetCode刷题指南》中的题目比起之间的C语言刷题集中的题目,肯定会更加复杂一些。而且题目形式也不一样,大家需要注意一下。如果文章对你有帮助的话,欢迎评论,点赞,收藏加关注,感谢大家的支持


网站公告

今日签到

点亮在社区的每一天
去签到