前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode每日一题:合并两个有序数组

LeetCode每日一题:合并两个有序数组

作者头像
利刃大大
发布2023-04-12 14:01:57
1320
发布2023-04-12 14:01:57
举报
文章被收录于专栏:编程语言/linux/算法
Alt
Alt

链接: 合并两个有序数组


这题有个要求:能不能使用O(m+n)的时间复杂度完成?

那当然是有的!

思路:用两个指针分别指向两个数组的尾部!这个很关键! 然后从后向前遍历。又题目可知,nums1的大小肯定是m+n的,且nums1的后半部分是空的,直接覆盖是没影响的。 所以就是将nums2中的元素与nums1中的比较,谁大就先放谁进去。

代码语言:javascript
复制
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1=m-1,p2=n-1;
        int i=1;
        while(p1>=0||p2>=0)
        {
            if(p1<0)
            {
                nums1[m+n-i]=nums2[p2];
                p2--;
                i++;
            }
            else if(p2<0)
            {
                break;
            }
            else if(nums1[p1]<=nums2[p2])
            {
                nums1[m+n-i]=nums2[p2];
                i++;
                p2--;
            }
            else 
            {
                nums1[m+n-i]=nums1[p1];
                p1--;
                i++;
            }
        }
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-07-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档