算法题:合并N个长度为L的有序数组为一个有序数组(JAVA实现)

昨天面试被问到这道算法题,一时没有回答上来,今天思考了一下,参阅了网上的教程,做了一个JAVA版本的实现。

方案一:

新建一个N*L的数组,将原始数组拼接存放在这个大数组中,再调用Arrays.sort()进行排序,或者使用其它排序方法即可。

此方法时间复杂度为o(N*Llog2N*L);

具体代码实现如下:

import java.util.Arrays;
class Solution {
    public static int[] MergeArrays(int[][] array) {
        int N = array.length, L;
        if (N == 0)
            return new int[0];
        else {
            L = array[0].length;
            for (int i = 1; i < N; i++)
                if (L != array[i].length)
                    return new int[0];
        }
        int[] result = new int[N * L];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < L; j++)
                result[i * L + j] = array[i][j];
        Arrays.sort(result);
        return result;
    }
}

方案二:

使用PriorityQueue实现最小堆,需要定义一个指针数组,用于保存这N个数组的index,定义Node类用于保存当前数值(value)和该数字所在的数组序号(idx),并且覆写Comparetor<Node>的compare方法实现自定义排序。PriorityQueue的offer()和poll()方法时间复杂度均为logn。

思路:首先将N个数组的第一位放到PriorityQueue,循环取出优先队列的首位(最小值)放入result数组中,并且插入该首位数字所在数组的下一个数字(如果存在),直到所有数字均被加入到result数组即停止(N*L)次。

时间复杂度:O(N*LlogN)

空间复杂度:O(N)

代码实现:

import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.Comparator;

public class SortedArraysMerge {
    static class Node {
        int value;
        int idx;

        public Node(int value, int idx) {
            this.value = value;
            this.idx = idx;
        }
    }

    public static int[] MergeArrays(int[][] arr) {
        int N = arr.length, L;
        if (N == 0)//此时传入数组为空
            return new int[0];
        else {//判断数组是否符合规范
            L = arr[0].length;
            for (int i = 1; i < N; i++)
                if (arr[i].length != L)
                    return new int[0]; //此时数组不规范
        }
        int[] result = new int[N * L];
        int[] index = new int[N];
        Arrays.fill(index, 0, N, 0);
        PriorityQueue<Node> queue = new PriorityQueue<Node>(new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2) {
                if (n1.value < n2.value)
                    return -1;
                else if (n1.value > n2.value)
                    return 1;
                else
                    return 0;
            }
        });
        for (int i = 0; i < N; i++) {
            Node node = new Node(arr[i][index[i]++], i);
            queue.offer(node);
        }
        System.out.println("" + queue.size());
        int idx = 0;
        while (idx < N * L) {
            Node minNode = queue.poll();
            result[idx++] = minNode.value;
            if (index[minNode.idx] < L) {
                queue.offer(new Node(arr[minNode.idx][index[minNode.idx]], minNode.idx));
                index[minNode.idx]++;
            }
        }
        return result;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑泽君的专栏

java基础和面向对象面试题_01

19620
来自专栏java达人

Java 8 Stream 教程 (二)

作者:Benjamin 译者:java达人 来源:http://winterbe.com/posts/2014/07/31/java8-stream-tuto...

256100
来自专栏菩提树下的杨过

字符编码-使用c#研究

微软的那个臭屁的JOEL(就是写《JOEL说软件》的那个牛人)曾说:“每一位软件开发人员必须、绝对要至少具备UNICODE与字符集知识(没有任何例外)”,我也常...

20270
来自专栏一个会写诗的程序员的博客

第4章 类与面向对象编程第4章 类与面向对象编程

在前面的章节中,我们学习了Kotlin的语言基础知识、类型系统等相关的知识。在本章节以及下一章中,我们将一起来学习Kotlin对面向对象编程以及函数式编程的支持...

9520
来自专栏Golang语言社区

Go语言与面向对象编程

学习Go语言差不多快两个月了,感觉这个过程还是蛮快乐的,翻翻英文资料,写写小程序,总是觉得有好多东西都搞不明白,一步步走下来,却发现,这些迷惑好像也是不可或缺的...

34880
来自专栏技术/开源

从C#到TypeScript - 高级类型

C# vs TypeScript - 高级类型 上一篇讲了基础类型,基本上用基础类型足够开发了,不过如果要更高效的开发,还是要看下高级类型,这篇和C#共同点并不...

22290
来自专栏静晴轩

JavaScript 字符串实用常操纪要

JavaScript 字符串用于存储和处理文本。因此在编写 JS 代码之时她总如影随形,在你处理用户的输入数据的时候,在读取或设置 DOM 对象的属性时,在操作...

40570
来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:表达式以及运算符

正文之前 好久没写了啊!!感觉自己都已经不爱简书了。不过其实我的《C++ Primer》已经看到400多页了。然而网络笔记还停留在120页,这个很骚啊,意味着我...

35270
来自专栏一个会写诗的程序员的博客

《Kotlin 程序设计》第六章 Kotlin 函数式编程(FP)第六章 Kotlin 函数式编程(FP)1. 函数式编程概述2. Kotlin函数式编程参考资料

从本质上来说, 程序就是一系列有序执行的指令集合。 如何将指令集合组织成可靠可用可信赖的软件(美妙的逻辑之塔), 这是个问题。

13560
来自专栏Golang语言社区

Go语言与面向对象编程

学习Go语言差不多快两个月了,感觉这个过程还是蛮快乐的,翻翻英文资料,写写小程序,总是觉得有好多东西都搞不明白,一步步走下来,却发现,这些迷惑好像也是不可或缺的...

45270

扫码关注云+社区

领取腾讯云代金券