Leetcode - Merge k Sorted Lists

``
Screenshot from 2016-01-23 15:58:48.png

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        else if (lists.length == 1)
            return lists[0];
        return divide(lists, 0, lists.length - 1); 
    }
    
    private ListNode divide(ListNode[] lists, int begin, int end) {
        if (end - begin + 1 < 2)
            return lists[begin];
        int middle = (begin + end) / 2;
        ListNode left = divide(lists, begin, middle);
        ListNode right = divide(lists, middle + 1, end);
        return mergeTwoLists(left, right);
    }
    
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        else if (l2 == null)
            return l1;
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                temp.next = l1;
                l1 = l1.next;
            }
            else {
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        temp.next = (l1 == null) ? l2 : l1;
        return dummy.next;
    }
}

我就是采用了merge sort 的思想,把這些lists先divide丹弱,到只剩下兩個的時候德撬,再merge一下。算了下復雜度躲胳,其實挺高的蜓洪。每個list都需要重復訪問多次把。
比如0, 1, 2, 3 條list
那么 0 ,1 merge坯苹, 2 和3 merge
然后 0,1組成的綜合體與2,3組成的綜合體再merge
這個時候又需要訪問下0,1,2,3隆檀。 有重復。時間復雜度應該比較高。雖然看測試下來刚操,效果還不錯。

后來看了一個新的解法再芋,復雜度要低很多菊霜。用priority queue 來做。
My code:

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() {
                public int compare(ListNode o1, ListNode o2) {
                    if (o1.val < o2.val)
                        return -1;
                    else if (o1.val == o2.val)
                        return 0;
                    else
                        return 1;
                }  
        });
        
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null)
                pq.add(lists[i]);
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode scanner = dummy;
        while (pq.size() > 0) {
            ListNode temp = pq.poll();
            scanner.next = temp;
            scanner = scanner.next;
            if (temp.next != null)
                pq.add(temp.next);
        }    
        return dummy.next;
    }
}

具體看下代碼就懂了济赎。復雜度是 log(k) * n
k = number of lists
n = number of all nodes

注意下這道題目用到了 PrioirtyQueue 這個數據結構鉴逞,并且可以自帶Comparator進去。
記得上次使用到的數據結構司训, TreeSet, 其實就是Binary search tree

參考網站:
http://www.programcreek.com/2013/02/leetcode-merge-k-sorted-lists-java/

Anyway, Good luck, Richardo!

My code:

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(8, new Comparator<ListNode>() {
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                pq.offer(lists[i]);
            }
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        while (!pq.isEmpty()) {
            ListNode curr = pq.poll();
            if (curr.next != null) {
                pq.offer(curr.next);
            }
            pre.next = curr;
            pre = curr;
        }
        
        return dummy.next;
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        System.out.println("111");
    }
}

how to initialize a PriorityQueue object

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(8, new Comparator<Integer>() {
    public int compare(Integer i1, Integer i2) {
        return i1.compareTo(i2);
    }
});

覺得用pq 來做這道題目是最好的构捡。

Anyway, Good luck, Richardo! -- 09/14/2016

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市壳猜,隨后出現(xiàn)的幾起案子勾徽,更是在濱河造成了極大的恐慌,老刑警劉巖统扳,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件喘帚,死亡現(xiàn)場離奇詭異,居然都是意外死亡咒钟,警方通過查閱死者的電腦和手機吹由,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來朱嘴,“玉大人倾鲫,你說我怎么就攤上這事∑兼遥” “怎么了乌昔?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長帚湘。 經常有香客問我玫荣,道長,這世上最難降的妖魔是什么大诸? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任捅厂,我火速辦了婚禮,結果婚禮上资柔,老公的妹妹穿的比我還像新娘焙贷。我一直安慰自己,他們只是感情好贿堰,可當我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布辙芍。 她就那樣靜靜地躺著,像睡著了一般。 火紅的嫁衣襯著肌膚如雪故硅。 梳的紋絲不亂的頭發(fā)上庶灿,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天,我揣著相機與錄音吃衅,去河邊找鬼往踢。 笑死,一個胖子當著我的面吹牛徘层,可吹牛的內容都是我干的峻呕。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼趣效,長吁一口氣:“原來是場噩夢啊……” “哼瘦癌!你這毒婦竟也來了?” 一聲冷哼從身側響起跷敬,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤讯私,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后干花,有當地人在樹林里發(fā)現(xiàn)了一具尸體妄帘,經...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年池凄,在試婚紗的時候發(fā)現(xiàn)自己被綠了抡驼。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡肿仑,死狀恐怖致盟,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情尤慰,我是刑警寧澤馏锡,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站伟端,受9級特大地震影響杯道,放射性物質發(fā)生泄漏。R本人自食惡果不足惜责蝠,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一党巾、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧霜医,春花似錦齿拂、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽吗购。三九已至,卻和暖如春砸狞,著一層夾襖步出監(jiān)牢的瞬間捻勉,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工刀森, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留贯底,地道東北人。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓撒强,卻偏偏與公主長得像,于是被迫代替她去往敵國和親笙什。 傳聞我的和親對象是個殘疾皇子飘哨,可洞房花燭夜當晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內容