Merge k sorted arrays

Leave a comment

August 23, 2016 by oneOokay

Given k sorted integer arrays, merge them into one sorted array.


用一个size为k的PriorityQueue来解决:

把每一个array的第一个元素放入到PriorityQueue里面,放完之后要pop出一个数,加入到result array中,再到pop出的数属于的array中,放入第二个元素。所以这里怎么根据pop出来的数找到它原来的array呢?这里就需要构造一个自定义class了,里面需要包含row,col,val就可以了。

接着写好priorityQueue的comparator就可以了。

整个的时间复杂度是O(Nlogk)。空间复杂度是O(k)。

  • PriorityQueue:O(log n) performance for inserts and removals
  • 由于priority queue的大小为始终为k,而每次插入的复杂度是log k,一共插入N个节点。时间复杂度为O(Nlogk),空间复杂度为O(k)
class Element{ //element之后没有括号
public int row; //public attribute 要加public
public int col;
public int val;
public Element(int r, int c, int v){
row = r;
col = c;
val = v;
}}

//Comparator的写法,从小到大排序left - right; 从大到小排序,right - left?
private Comparator<Element> ElementComparator = new Comparator() {
public int compare(Element left, Element right) {
return left.val - right.val;
}}; 
public List mergekSortedArrays(int[][] arrays) {
if (arrays == null || arrays.length <= 0) {
return null;}

Queue Q = new PriorityQueue(arrays.length, 
ElementComparator);
int total = 0;
for (int i = 0; i < arrays.length; i ++) {  if (arrays[i].length > 0)
{
Element elem = new Element(i, 0, arrays[i][0]);
Q.add(elem);
total += arrays[i].length;
}}
List result = new ArrayList(); 
int index = 0;
while (!Q.isEmpty()){
Element elem = Q.poll();
result.add(elem.val);
if (elem.col + 1 < arrays[elem.row].length) 
//当前的element不是数组中最后一个元素时
{
elem.col += 1;
elem.val = arrays[elem.row][elem.col];
Q.add(elem);
}}
return result;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: