Zenn
📚

LeetCode 2020-11-02: Insertion Sort List

2020/11/04に公開
Java
LeetCode
tech

LeetCode の daily problem に挑戦した記録です。

今日の問題は Insertion Sort List (medium)。

問題の概要

考え方

  • ソート対象のデータ構造が配列ではなく (単方向の) 連結リストである点に注意すれば、挿入ソート自体は基本中の基本のアルゴリズムなので、コンピュータサイエンスを学んだことがある人なら容易に解けますね
    • 配列の場合は、ソート済みの末尾から比較を行いつつ要素をずらしていくけど、連結リストの場合は先頭から走査して挿入位置を見つければ OK
  • まずはナイーブな実装をして submit → accept 👍
    • Runtime 31ms で Your runtime beats 19.72 % of java submissions. とか。えぇぇ… 🤮
  • 普通の挿入ソートの最悪計算量は O(n^2) なので、まあそういう極端な例がテストケースに存在するとしたらこれは仕方ないかな
    • 特に、ソート済みの連結リストが与えられた場合が最悪ケースに相当する
  • 意地悪なテストケースへのちょっとした対策を仕込んでみよう
    • ソート済みの領域のすぐ右隣にある要素が、ソート済み領域の末尾より大きい要素かどうかをチェックして真であればソート済み領域の末尾にくっつけるようにする
  • この改良をして submit → accept 👍
    • Runtime は 3ms まで減少
    • それでもまだ Your runtime beats 77.90 % of java submissions. でしかない 😢
  • さらなる改善をしてみよう
    • 一回のループで一個の要素の挿入箇所を探して挿入、とする代わりに、一回のループで 複数個の要素 の挿入箇所を探して挿入してみればいいのでは？ 🤔
      • もはや挿入ソートじゃない気がするけど、気にしたら負けかな 😇
    • 「複数個の要素」は、未ソート済みの先頭から続く単調増加する部分としよう
      • これにより、挿入箇所の探索と挿入は二つのリストのマージ操作で実現できるようになる 💪
  • 早速実装して submit → accept
    • Runtime 2ms 達成できたが、Your runtime beats 98.41 % of java submissions.
    • このあたりが限界かな…
  • 上位陣のサンプルコードを拝見してみよう
    • うーんこれは Arrays.sort() 使っていてもはや挿入ソートでもなんでもないですね…
    • 0ms のこれも冒頭で「マージソートである」と宣言してしまってるなあ… 🤦‍♂️

コード

ナイーブな実装

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode();

        while (head != null) {
            ListNode node = dummy;
            ListNode insNode = head;
            head = head.next;
            insNode.next = null;

            while (node.next != null) {
                if (node.next.val > insNode.val) {
                    break;
                }
                node = node.next;
            }

            if (node.next != null) {
                insNode.next = node.next;
            }
            node.next = insNode;

        }

        return dummy.next;
    }
}

ソート済み連結リストに対する対策

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode last = null;

        while (head != null) {
            ListNode node = dummy;
            ListNode insNode = head;
            head = head.next;
            insNode.next = null;

            while (node.next != null && node.next.val < insNode.val) {
                node = node.next;
            }

            insNode.next = node.next;
            node.next = insNode;

            if (last == null || last.val < insNode.val) {
                last = insNode;
            }

            while (head != null && last.val < head.val) {
                last.next = head;
                last = head;
                head = head.next;
            }
            last.next = null;
        }

        return dummy.next;
    }
}

複数個同時に挿入処理のループを回す実装

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        head = head.next;
        dummy.next.next = null;

        while (head != null) {
            ListNode l1 = dummy;
            ListNode l2 = head;
            while (head.next != null && head.next.val >= head.val) {
                head = head.next;
            }

            ListNode ta = head.next;
            head.next = null;
            head = ta;

            while (l1.next != null && l2 != null) {
                while (l1.next != null && l1.next.val <= l2.val) {
                    l1 = l1.next;
                }
                ListNode tb = l1.next;
                l1.next = l2;
                l2 = l2.next;
                l1.next.next = tb;
                l1 = l1.next;
            }
            if (l2 != null) {
                l1.next = l2;
            }
        }

        return dummy.next;
    }
}

Discussion