[LeetCode/Hard] 23. Merge k Sorted Lists (JAVA)

15791 ワード
ProblemSolving アルゴリズム#アルゴリズム# leetcode テキストリンク

質問する


に答える


メインプール:1つずつマージ


最初に思いついた答えは,2つのListNodeをmerge sortに統合し,k-1回繰り返したことである.2つのListNodeの組み合わせをanswerに保存し、answerと次のListNodeとを組み合わせてanswerを更新する.
この解の時間的複雑さはO(nk)であった.n回探索k-1回繰り返すからです.また,空間複雑度はO(1)であった.余分なスペースがないからです.
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode answer = null;
        
        int idx = 0;
        while (idx < k)
            answer = merge(answer, lists[idx++]);
        
        return answer;
    }
    
    private ListNode merge(ListNode left, ListNode right) {
    
        if (left == null) return right;
        if (right == null) return left;
        
        ListNode merged = null;
        if (left.val <= right.val) {
            merged = left;
            left = left.next;
        } else {
            merged = right;
            right = right.next;
        }
        
        ListNode current = merged;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                current.next = left;
                left = left.next;
            } else {
                current.next = right;
                right = right.next;
            }
            current = current.next;
        }
        
        if (left != null) current.next = left;
        if (right != null) current.next = right;
        
        return merged;
    }
}
しかし、LeetCodeに上記のコードを提出すると...

実行時の効率はゴミです!だから、もっといい方法があるのか悩んでいます.

二次解:二次連結

k個のListNodeペアを結合し、結合回数をlog(k)に減少させた.例えば、8個のListNodeを結合する場合、2個を4個のListNodeに結合し、さらに4個を2個に結合し、2個を1個に結合する.これにより時間の複雑さはO(nlog(k))に大幅に減少した.
コードはわずかmergeKLists()でわずかに変動し,merge()は最初の解と同じである.
class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;     
        
        int interval = 1;
        while (interval < k) {
            int idx = 0;
            while (idx + interval < k) {
                lists[idx] = merge(lists[idx], lists[idx+interval]);
                idx += interval * 2;
            }
            interval *= 2;
        }
        return k == 0 ? null : lists[0];
    }
    
    private ListNode merge(ListNode left, ListNode right) {
    
        if (left == null) return right;
        if (right == null) return left;
        
        ListNode merged = null;
        if (left.val <= right.val) {
            merged = left;
            left = left.next;
        } else {
            merged = right;
            right = right.next;
        }
        
        ListNode current = merged;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                current.next = left;
                left = left.next;
            } else {
                current.next = right;
                right = right.next;
            }
            current = current.next;
        }
        
        if (left != null) current.next = left;
        if (right != null) current.next = right;
        
        return merged;
    }
}
運行時間が著しく減少していることを確認できます!

リファレンス


Merge K Sorted Lists
CodeKata 16
アプリケーションを完全に終了する方法で、すべてのActivityとサービスを終了します.