lintcode486. 合并k个排序数组

电玩女神 2023-07-06 06:12 1阅读 0赞

将 k 个有序数组合并为一个大的有序数组。

样例
    样例 1:
    
    输入:
      [
        [1, 3, 5, 7],
        [2, 4, 6],
        [0, 8, 9, 10, 11]
      ]
    输出: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
    样例 2:
    
    输入: 
      [
        [1,2,3],
        [1,2]
      ]
    输出: [1,1,2,2,3]
    挑战
    在 O(N log k) 的时间复杂度内完成：
    
    N 是所有数组包含的整数总数量。
    k 是数组的个数。

class Solution {
        
    public:
        /**
         * @param arrays: k sorted integer arrays
         * @return: a sorted array
         */
        vector<int> mergekSortedArrays(vector<vector<int>> &arrays) {
        
            // write your code here
            if(arrays.size()<=0) return vector<int>();
            return help(arrays,0,arrays.size()-1);
        }
        vector<int> merge(vector<int> a,vector<int> b)
        {
        
            vector<int>res;
            int ai=0;
            int bi=0;
            while(ai<a.size())
            {
        
                res.push_back(a[ai]);
                ai++;
            }
            while(bi<b.size())
            {
        
                res.push_back(b[bi]);
                bi++;
            }
            sort(res.begin(),res.end());
            return res;
        }
        vector<int> help(vector<vector<int>>arrays,int l,int r)
        {
        
            if(l==r) return arrays[l];
            else if(l+1==r) return merge(arrays[l],arrays[r]);
            else
            {
        
                int mid=l+(r-l)/2;
                vector<int> left=help(arrays,l,mid);
                vector<int> right=help(arrays,mid+1, r);
                return merge(left,right);
            }
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode486. 合并k个排序数组

将 k 个有序数组合并为一个大的有序数组。样例样例 1: 输入: [ [1, 3, 5, 7],

电玩女神/ 2023年07月06日 06:12/ 0 赞/ 2 阅读

相关 lintcode 104. 合并k个排序链表优先队列

合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。样例样例 1: 输入: [2->4->null,null,-1->nul

傷城~/ 2023年07月03日 07:08/ 0 赞/ 2 阅读

相关【LintCode 简单】64. 合并排序数组

1.问题描述：合并两个排序的整数数组A和B变成一个新的数组。注意事项你可以假设A具有足够的空间（A数组的大小大于或等于m+n）去添加B中的元素。

川长思鸟来/ 2022年06月01日 09:14/ 0 赞/ 196 阅读

相关【LintCode 简单】6. 合并排序数组 II

1.问题描述：合并两个排序的整数数组A和B变成一个新的数组。 2.样例：给出A=\[1,2,3,4\]，B=\[2,4,5,6\]，返回 \[1,2,2,3,4

客官°小女子只卖身不卖艺/ 2022年06月01日 05:55/ 0 赞/ 182 阅读

相关【LintCode 简单】165. 合并两个排序链表

1.问题描述：将两个排序链表合并为一个新的排序链表。 2.样例: 给出 `1->3->8->11->15->null`，`2->null`，返回 `1->2->

小灰灰/ 2022年06月01日 04:08/ 0 赞/ 186 阅读

相关 LintCode -- 合并排序数组 II

描述合并两个排序的整数数组A和B变成一个新的数组。样例给出A=\[1,2,3,4\]，B=\[2,4,5,6\]，返回 \[1,2,2,3,4,4,5,6\

朴灿烈づ我的快乐病毒、/ 2022年05月25日 11:12/ 0 赞/ 195 阅读

相关合并 k 个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入: [ 1->4->5, 1->3->4,

傷城~/ 2022年04月22日 11:46/ 0 赞/ 154 阅读

相关合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入: [ 1->4->5, 1->3->4,

男娘i/ 2022年01月20日 04:07/ 0 赞/ 190 阅读

相关合并K个排序链表

题目描述合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 输入: [ 1->4->5, 1->

雨点打透心脏的1/2处/ 2022年01月14日 23:35/ 0 赞/ 205 阅读

相关合并K个排序链表

合并K个排序链表题目描述 ![5057999-3fd09622a0f9a1f2.png][] 基本思路这道题属于双链表合并的进阶。理解这道题首先需要了解

清疚/ 2021年10月01日 11:26/ 0 赞/ 278 阅读