`

Merge K sorted arrays

 
阅读更多

Input: N sorted arrays of integers (in ascending order)

Output: Final sorted array of integers

 

public static class Node {
    int index = 0;
    List<Integer> list;
    public Node(List<Integer> list) {
        this.list = list;
    }
    
    public int peek() {
        return list.get(index);
    }

    public int next() {
        return list.get(index++);
    }
    
    public boolean hasNext() {
        return index < list.size();
    }
}
List<Integer> sortData(List<List<Integer>> numArray) {
    List<Integer> result = new ArrayList<>();
    Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>(){
        public int compare(Node n1, Node n2) {
            return n1.peek() - n2.peek();
        }
    });
    for(List<Integer> list:numArray) {
        if(list != null && list.size() > 0) {
            queue.offer(new Node(list));
        }
    }
    while(!queue.isEmpty()) {
        Node node = queue.poll();
        result.add(node.next());
        if(node.hasNext()) {
            queue.offer(node); 
        }
    }
    return result;
}

 

分享到:
评论

相关推荐

    Coding Interview in Java

    21. 查找算法问题:比如Range Addition(范围加法)、Merge K Sorted Arrays in Java(在Java中合并K个排序数组)等。 这些知识点覆盖了数据结构和算法的各个方面,从基础的数组、字符串操作到复杂的动态规划、二分...

    程序员面试宝典LeetCode刷题手册

    第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters ...23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli

    归并排序

    主要是两步,先把数组分成两半(merge),再把这两半合并成有序的数组(mergeTwoSortedArrays)。 temp参数的作用是接收排序后的数组,然后再把值一一付给原数组,如果不加这个参数,我们就需要重复开辟空间,或者...

    leetcode分类-leetcode:leetcode问题的代码

    Arrays 地图 #1:Two Sum #3:Longest Substring Without Repeating Characters #5:Longest Palindromic Substring 链表 #2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:Longest Substring Without ...

    Coding Interview In Java

    7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two ...

    lrucacheleetcode-leetcode:leetcode

    Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 12. Integer to Roman 13. Roman to Integer 14. Longest Common Prefix 15. 3Sum 20. Valid ...

    leetcode2sumc-Data-Structures-and-Algorithms:数据结构和算法

    sorted arrays length = len ( arr1 ) + len ( arr2 ) res = [ None for _ in range ( length )] i1 , i2 = 0 , 0 for i in range ( length ): if i2 == len ( arr2 ) or i1 &lt; len ( arr1 ) and arr1 [ i1 ] &lt;...

    将两数组合并成一个数组并排序

    在这个例子中,我们首先定义了两个已排序的数组`A`和`B`,然后调用了`merge_sorted_arrays`函数进行合并。最后,通过循环打印出合并并排序后的数组`C`。 这个操作在处理大量数据时尤其有用,例如在数据库查询、数据...

    leetcode添加元素使和等于-leetcode:我的leetcode解决方案

    Arrays Trapping Rain Water Integer to English Words Regular Expression Matching Merge K Sorted Lists Remove Invalid Parentheses Serialize and Deserialize Binary Tree Minimum Window Substring C++ STL中...

    leetcode双人赛-LeetCode:力扣笔记

    Arrays 困难 数学 Longest Palindromic Substring 中等 回文 ZigZag Conversion 中等 矩阵 重要 Reverse Integer 简单 字串 String to Integer (atoi) 中等 字串 麻烦 Palindrome Number 简单 字串 Container With ...

    matlab开发-Mergesortedarrays

    function sortedArray = merge_sorted_arrays(arr1, arr2) % 初始化新数组和双指针 sortedArray = []; i = 1; j = 1; % 当两个指针都在有效范围内时循环 while i (arr1) && j (arr2) % 比较当前元素,选择较...

    leetcode中文版-LeetCode:LeetcodeC++/Java

    Arrays 两个排序数组的中位数 ary,binary search,dive and conquer 5 Longest Palindromic Substring 最长回文子串 string,dp 8 String to Integer(atoi) 字符串转整数 string 13 Roman to Integer 罗马数字转整数 ...

    lrucacheleetcode-Algorithm:一些常见的算法的解题报告

    Arrays 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 11.Container With Most Water 14.Longest Common Prefix 15.3Sum 16.3Sum Closest 19.Remove Nth Node From End of List 20.Valid ...

    leetcode2-Leetcode:Leetcode_answer

    Arrays JavaScript O(log (m+n)) O(1) Hard 7 Reverse Integer JavaScript O(n) O(1) Easy 9 Palindrome Number JavaScript O(n) O(1) Easy 19 Remove Nth Node From End of List JavaScript O(n) O(1) Medium 21 ...

    lrucacheleetcode-geekbang-algorithms:geekbang-算法

    lru cache leetcode Class 1 数组 时间复杂度 根据下标查询 Lookup ...要求:对nums1进行inplace处理,并且已经为nums1开辟好了...arrays nums1 and nums2, the goal is to merge them into a single sorted array,

    c代码-两有序数组合并排序--冒泡

    在这个`merge_sorted_arrays`函数中,我们首先初始化了两个指针`i`和`j`,分别对应`arr1`和`arr2`的起始位置,以及一个指针`k`用于记录合并后数组的当前位置。然后,我们通过两个`while`循环,分别处理两个数组的...

    LeetCode 刷题汇总1

    * 两个排序数组的中位数(Median of Two Sorted Arrays):计算两个排序数组的中位数。 * 整数到罗马(Integer to Roman):将整数转换为罗马数字。 * 罗马到整数(Roman to Integer):将罗马数字转换为整数。 4...

    javalruleetcode-LeetCode::lollipop:个人LeetCode习题解答仓库-多语言

    Arrays 5 Longest Palindromic Substring 8 String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted...

Global site tag (gtag.js) - Google Analytics