s*********s
发帖数: 318 | 1 1. merger sort a single linked list
2. find minimum k from two sorted array
我写得又长又臭，求短小精悍，清晰易懂的C++ codes. | a***n
发帖数: 538 | 2 第二题
int findKthSmallest(int A[], int m, int B[], int n, int k) {
if (m>n) return findKthSmallest(B,n,A,m,k);
if (m==0) return B[k-1];
if (k==1) return min(A[0], B[0]);
int i = min(m-1,k/2);
int j = k-1-i;
int Ai_1 = (i==0)?INT_MIN:A[i-1];
int Bj_1 = (j==0)?INT_MIN:B[j-1];
int Ai = (i==m)?INT_MAX:A[i];
int Bj = (j==n)?INT_MAX:B[j];
if(Ai_1
if(Bj_1
if(Ai==Bj) return Ai;
if (Ai
return findKthSmallest(A,i,B+j+1, n-j-1, k-j-1);
} | e*******s
发帖数: 1067 | | j********x
发帖数: 2330 | | b******7
发帖数: 92 | 5 1. merger sort a single linked list
template
ListNode * mergeHelper(ListNode * left, ListNode * right)
{
assert(left != NULL && right != NULL);
ListNode * head = NULL;
if(left->val < right->val)
{
head = left;
left = left->next;
}
else
{
head = right;
right = right->next;
}
while( left != NULL && right != NULL)
{
if(left->val < right->val)
{
head->next = left;
left = left->next;
}
else
{
head->next = right;
right = right->next;
}
head = head->next;
}
head->next = (left != NULL) ? left : right;
return head;
}
template
pair *, ListNode *> partitionHelper(ListNode * head)
{
assert(head != NULL && head->next != NULL);
ListNode * slow = head;
ListNode * fast = head;
while(fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
return make_pair(head, slow);
}
template
ListNode * mergeSort(ListNode * head)
{
if(head == NULL || head->next == NULL)
return head;
auto r = partitionHelper(head);
ListNode * left = mergeSort(r.first);
ListNode * right = mergeSort(r.second);
return mergeHelper(left, right);
}
2. find minimum k from two sorted array
template
T findkthElem(T A[], int len1, T B[], int len2, int k)
{
assert(k> 0 && k <=len1+len2 && len1 >= 0 && len2 >= 0);
if(len1 == 0) return B[k-1];
if(len2 == 0) return A[k-1];
if(k == 1) return min(A[0], B[0]);
int k1 = k/2;
int k2 = k - k1;
if(k1 > len1)
{
k1 = len1;
k2 = k - k1;
}
if(k2 > len2)
{
k2 = len2;
k1 = k - k2;
}
if(A[k1-1] < B[k2-1])
{
return findkthElem(A+k1, len1 - k1, B, len2, k2);
}
else
{
return findkthElem(A,len1, B+k2, len2-k2, k1);
}
} | s*********s
发帖数: 318 | | s*********s
发帖数: 318 | 7 学习重写了一遍。不太理解 partitionHelper为什么要返回head in the pair?在
mergeSort()里,
ListNode *left = mergeSort(head);
就可以了吧？
另外，这个megersort的复杂度是O(NlgN)?
【在 b******7 的大作中提到】
: 1. merger sort a single linked list
: template
: ListNode * mergeHelper(ListNode * left, ListNode * right)
: {
: assert(left != NULL && right != NULL);
: ListNode * head = NULL;
: if(left->val < right->val)
: {
: head = left;
: left = left->next;
|
|
