lurenaa的博客

🥩自顶向下归并排序

  基础版，根据算法4中的数组的归并算法改得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return head; 
        n = 1;
         ListNode* h = head;
        while(h->next != NULL) {
            h = h->next;
            ++n;
        }
        //cout << "count : " << n  << endl;
        aux = new int[n]();
        sortList(head, 0, n - 1);
        return head;
    }
    void sortList(ListNode* head, int i, int j) {
        if(i >= j) return ;
        int mid = i + (j - i) / 2; 
        sortList(head, i, mid);
        sortList(head, mid + 1, j);
        merge(head, i, mid, j);
    }
    void merge(ListNode* head, int i,int mid, int j) {
        //cout << "i,m.j : " << i << " " << mid << " " << j << endl;
        ListNode* inode = at(head, i),* inode2 = inode;
        //cout << "inode->val: " <<  inode2->val << endl;
        int lo = i - i, hi = mid + 1 - i;
        for(int k = 0; k <= j - i; ++k , inode = inode->next)
            aux[k + i] = inode->val;
        // for(int k = i; k <= j; ++k) {
            //cout << aux[k] << " ";
        // }
        //cout << endl;
        for(int k = 0; k <= j - i; ++k) {
            if(lo > mid - i){ 
                inode2->val = aux[hi + i];
                ++hi;
            }
            else if (hi > j - i) {
                inode2->val = aux[lo + i];
                ++lo;
            }
            else if (aux[lo + i] > aux[hi + i]) {
                inode2->val = aux[hi + i];
                ++hi;
            } else {
                inode2->val = aux[lo + i];
                ++lo;
            }
            //cout << "lo, hi : " << lo <<  " " << hi << endl;
            inode2 = inode2->next;
        }
    }
    ListNode* at(ListNode* head, int n) {
        while(n--)
            head = head->next;
        return head;
    } 
    int* aux;
    int n;
};

Accepted

16/16 cases passed (1108 ms)

Your runtime beats 5.09 % of cpp submissions

Your memory usage beats 62.56 % of cpp submissions (12.3 MB)

🥧自顶向下归并排序2

  学习自链接,以一种链表得方式来做，而不是以数组得方式来思考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* slow = head, 
            * fast = head->next;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* tmp = slow->next;
        slow->next = nullptr;
        ListNode* left = sortList(head);
        ListNode* right = sortList(tmp);
        ListNode thead = ListNode(-1), *thd = &thead;
        while(left || right) {
            if(!left) {
                thd->next = right;
                right = right->next;
            } else if(!right) {
                thd->next = left;
                left = left->next;
            } else if (right->val > left->val) {
                thd->next = left;
                left = left->next;
            } else {
                thd->next = right;
                right = right->next;
            }
            thd = thd->next;
        }
        return thead.next;
    }
    
};

Accepted

16/16 cases passed (24 ms)

Your runtime beats 100 % of cpp submissions

Your memory usage beats 72.66 % of cpp submissions (11.9 MB)

🥣自底向上归并排序

  学习自链接，自底向上得链表，有几个难点:

  • 如何每次merge后与后面得链表接上
  • 如何串联成一个长得链表最后返回
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if(!head || !head->next)
                return head;
            ListNode* preNode = new ListNode(0), *pre = preNode;
            pre->next = head;
            int count = 0;
            while((pre = pre->next) && ++count) ;
            // cout << "count : " << count << endl;
            pre = preNode;
            for(int sz = 1; sz < count; sz *=2) {
                while(pre = sortList(pre, sz)) ;
                pre = preNode;
            }
            return preNode->next;
        }

        ListNode* sortList(ListNode* pre, int sz) {
            ListNode* fl = pre->next, 
                *ll = pre->next;
            for(int i = 0; i < sz ; ++i) {
                if(!ll) 
                    return nullptr;
                ll =ll->next;
            }
            int lc = 0, fc = 0;
            while(fc < sz) {
                if(lc == sz || ll == nullptr || ll->val > fl->val) {
                    ++fc;
                    pre->next = fl;
                    fl = fl->next;
                } else {
                    ++lc;
                    pre->next = ll;
                    ll = ll->next;
                }
                pre = pre->next;
            }

            while(lc < sz && ll) {
                ++lc;
                pre->next = ll;
                ll = ll->next;
                pre=pre->next;
            }
            pre->next = ll;
            return pre;
        }
    };

    Accepted

    16/16 cases passed (24 ms)

    Your runtime beats 100 % of cpp submissions

    Your memory usage beats 93.48 % of cpp submissions (11.5 MB)


 上一页

LeetCode