LeetCode Online JudgeテーマC#練習-Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

        public class ListNode

        {

             public int val;

             public ListNode next;

             public ListNode() { }

             public ListNode(int x)

             {

                 this.val = x;

             }

        };    

ListNodeの実装.

 1         public static ListNode MergekSortedLists(List<ListNode> lists)

 2         {

 3             ListNode head = new ListNode();

 4             ListNode curr = head;

 5 

 6             if (lists.Count == 0)

 7                 return null;

 8 

 9             while (lists.Count > 0)

10             {

11                 while (lists.Count > 0 && lists[0] == null)

12                 {

13                     lists.RemoveAt(0);

14                 }

15                 if (lists.Count == 0)

16                     return null;

17                 ListNode minNode = lists[0];

18                 int listnum = 0;

19                 for (int i = 1; i < lists.Count; i++)

20                 {

21                     while (i < lists.Count && lists[i] == null)

22                         lists.RemoveAt(i);

23 

24                     if (i < lists.Count && minNode.val > lists[i].val)

25                     {

26                         minNode = lists[i];

27                         listnum = i;

28                     }

29                 }

30                 curr.next = minNode;

31 

32                 if (lists[listnum].next != null)

33                     lists[listnum] = lists[listnum].next;

34                 else

35                     lists.RemoveAt(listnum);

36 

37                 curr = curr.next;

38             }

39 

40             return head.next;

41         }

コード解析:
初めて作った時に書いたコードです.Mergeが最小のListNodeを使用した後、List< ListNode>でこのListNodeをRemoveします.しかしListのRemove法は時間的複雑度がO(n)であり,アルゴリズム全体がO(n 2)となる.復習中にこの問題を発見したので、次のコードがありました.

 1         public static ListNode MergekSortedLists2(List<ListNode> lists)

 2         {

 3             ListNode head = new ListNode();

 4             ListNode curr = head;

 5 

 6             //count how many empty Linked List in our list(vector)

 7             int numempty = 0;

 8 

 9             if (lists.Count == 0)

10                 return null;

11 

12             ListNode minNode = null;

13             int start = 0;

14             while (numempty < lists.Count)

15             {

16                 numempty = 0;

17 

18                 int listnum = -1;

19                 //get the first non-null listnode

20                 for (int i = 0; i < lists.Count; i++)

21                 {

22                     if (lists[i] != null)

23                     {

24                         minNode = lists[i];

25                         listnum = i;

26                         start = i + 1;

27                         break;

28                     }

29                     else

30                         numempty++;

31 

32                     start = i + 1;

33                 }

34 

35                 //get the smallest listnode

36                 for (int i = start; i < lists.Count; i++)

37                 {

38                     if (lists[i] != null && lists[i].val < minNode.val)

39                     {

40                         minNode = lists[i];

41                         listnum = i;

42                     }

43                 }

44 

45                 if (listnum < 0)

46                     return head.next;

47 

48                 lists[listnum] = lists[listnum].next;

49                 if(lists[listnum] == null)

50                     numempty++;

51 

52                 curr.next = minNode;

53                 curr = curr.next;

54             }

55 

56             return head.next;

57         }

コード解析:
While Loopでnumemptyの変数を維持し、numemtpy>=listsの数を数える.Count、つまりlistsにはListNodeがありません.戻るnext(headは、以下のListNodeに接続するために独自に作成された一時ListNodeである).
他の人のブログで役に立つpriorityを見ましたqueuedのやり方は、もちろんC++で、C#には内蔵のpriority queueはありません.でもpriority_queueの挿入はO(n)で、min_でもHeapもO(log(n))、時間、空間の複雑さが増え、比較的実現しやすいですが.