d********e
发帖数: 239 | 1 leedcode上的题目sort list
space要求O(1)
找了半天，都是recursive的方法
请哪个大牛能贴一个iterative的代码吧
谢谢 | c*******7
发帖数: 438 | 2 /**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if(head == null) {
return null;
}
ListNode[] heads = new ListNode[100];
int[] counts = new int[100];
heads[0] = head;
counts[0] = 1;
ListNode next = head.next;
int index = 1;
while(next != null) {
ListNode temp = next.next;
next.next = null;
heads[index] = next;
counts[index] = 1;
for(int i=index; i>=1; i--) {
if(counts[i] == counts[i-1]) {
heads[i-1] = merge(heads[i-1], heads[i], counts[i-1],
counts[i]);
counts[i-1] *= 2;
index--;
}
else {
break;
}
}
index++;
next = temp;
}
for(int i=index-1; i>=1; i--) {
heads[i-1] = merge(heads[i-1], heads[i], counts[i-1], counts[i]);
counts[i-1] = counts[i-1] + counts[i];
}
return heads[0];
}
private ListNode merge(ListNode l, ListNode r, int leftLength, int
rightLength) {
ListNode head = null;
ListNode tail = null;
while(leftLength != 0 && rightLength != 0) {
if(l.val < r.val) {
if(head == null) {
head = l;
tail = head;
}
else {
tail.next = l;
tail = l;
}
l = l.next;
leftLength--;
}
else {
if(head == null) {
head = r;
tail = head;
}
else {
tail.next = r;
tail = r;
}
r = r.next;
rightLength--;
}
}
while(leftLength != 0) {
tail.next = l;
tail = l;
l = l.next;
leftLength--;
}
while(rightLength != 0) {
tail.next = r;
tail = r;
r = r.next;
rightLength--;
}
tail.next = null;
return head;
}
} | c*******7
发帖数: 438 | | d********e
发帖数: 239 | 4 谢谢
recursive
不就是先找到中点
然后分别mergesort左边和右边
然后再合并？
【在 c*******7 的大作中提到】
: 顺便请教一下recrusive怎么做？
| c*******7
发帖数: 438 | 5 那样应该需要O(n^3)了吧？用Bubble sort更快一些。 | d********e
发帖数: 239 | 6 ListNode *sortList(ListNode *head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if(head == NULL || head->next == NULL) {
return head;
}
ListNode* mid = head;
ListNode* end = head;
while(end->next){
end = end->next;
if (end->next == NULL)
break;
end = end->next;
mid = mid->next;
}
ListNode* right = mid->next;
mid->next = NULL;
mid = right;
ListNode* left = sortList(head);
right = sortList(mid);
ListNode* dummy = new ListNode(1);
ListNode* tail = dummy;
while(left && right){
if (left->val < right->val){
tail->next = left;
left = left->next;
}
else{
tail->next = right;
right = right->next;
}
tail = tail->next;
}
if (left)
tail->next = left;
if (right)
tail->next = right;
return dummy->next;
}
【在 c*******7 的大作中提到】
: 那样应该需要O(n^3)了吧？用Bubble sort更快一些。
| c******w
发帖数: 1108 | 7 是O(nlogn)
每一层recursion的总复杂度是O(n)
一共有O(logn)层
【在 c*******7 的大作中提到】
: 那样应该需要O(n^3)了吧？用Bubble sort更快一些。
| x****g
发帖数: 1512 | | p**o
发帖数: 3409 | 9 def mergesort_topdown (aList):
""" Top-down merge sort.
A total of logn splits;
in each split we merge n items.
So the complexity is O(n logn).
"""
_splitmerge (aList, 0, len(aList))
def _splitmerge (aList, i, j):
""" Recursively split runs into two halves
until run size == 1 (considered sorted), then
merge two halves and return back up the call chain.
"""
if j - i > 1:
m = (i + j) // 2
_splitmerge (aList, i, m)
_splitmerge (aList, m, j)
_merge (aList, i, m, j)
def mergesort_bottomup (aList):
""" The bottom-up version of merge sort.
w = 1, 2, 4, 8, ...,
i = 0, 2w, 4w, 8w, ...,
= 0, 2, 4, 8, ...,
= 0, 4, 8, 16, ...,
= 0, 8, 16, 32, ...,
= ...
Pay attention to how the bounds are chosen.
"""
n = len(aList)
w = 1 # width
while w < n:
i = 0
while i < n:
k = min(n, i + w) # mid
j = min(n, i + w*2)
if j - i >= 2:
_merge (aList, i, k, j)
i += w * 2
w *= 2
def _merge (a, i, m, j):
b = [None] * (j-i)
ii, jj = i, m
for k in xrange(j-i):
if ii < m and (jj >= j or
a[ii] <= a[jj]):
b[k] = a[ii]
ii += 1
else:
b[k] = a[jj]
jj += 1
a[i:j] = b
if __name__ == '__main__':
a = [54,20,93,17,77,31,44,55,20]
mergesort_topdown (a)
print a
a = [54,20,93,17,77,31,44,55,20]
mergesort_bottomup (a)
print a | p**o
发帖数: 3409 | 10 哦，是特指那道leetcode链表题啊。我以为是通用的排序算法，就直接copy/paste了。 |
|
