- 论坛徽章:
- 8
|
今日面试题:
一个很大的2D矩阵,如果某点的值,由它周围某些点的值决定,例如下一时刻(i,j) 的值取当前时刻它的8邻点的平均,那么怎么用MapReduce来实现。
=====================
快排单链表分析
题目:
快排(QuickSort)单向链表(Singly Linked List)。
分析:
思路和数据的快速排序一样,都需要找到一个pivot元素、或者节点。然后将数组或者单向链表划分为两个部分,然后递归分别快排。
针对数组进行快排的时候,交换交换不同位置的数值,在分而治之完成之后,数据就是排序好的。那么单向链表是什么样的情况呢?除了交换节点值之外,是否有其他更好的方法呢?可以修改指针,不进行数值交换。这可以获取更高的效率。
在修改指针的过程中,会产生新的头指针以及尾指针,要记录下来。在partition之后,要将小于pivot的的部分、pivot、以及大于pivot的部分重新串起来成为一个singly linked list。
在partition时,我们用最后的节点作为pivot。当我们扫描链表时,如果节点值大于pivot,将节点移到尾部之后;如果节点小于,保持不变。
在递归排序时,我们先调用partition将pivot放到正确的为止并返回pivot,然后,递归左边,递归右边,最后在合成一个单链表。
C++实现:
struct node *partition(struct node *head, struct node *end,
struct node **newHead, struct node **newEnd)
{
struct node *pivot = end;
struct node *prev = NULL, *cur = head, *tail = pivot;
while(cur != pivot)
{
if(cur->data < pivot->data)
{
if((*newHead) == NULL)
(*newHead) = cur;
prev = cur;
cur = cur->next;
}
else
{
if(prev)
prev->next = cur->next;
structnode *tmp = cur->next;
cur->next = NULL;
tail->next = cur;
tail = cur;
cur = tmp;
}
}
if((*newHead) == NULL)
(*newHead) = pivot;
(*newEnd) = tail;
return pivot;
}
struct node *quickSortRecur(struct node *head, struct node *end)
{
if(!head || head == end)
return head;
node *newHead = NULL, *newEnd = NULL;
struct node *pivot = partition(head, end, &newHead, &newEnd);
if(newHead != pivot)
{
struct node *tmp = newHead;
while(tmp->next != pivot)
tmp = tmp->next;
tmp->next = NULL;
newHead = quickSortRecur(newHead, tmp);
tmp = getTail(newHead);
tmp->next = pivot;
}
pivot->next = quickSortRecur(pivot->next, newEnd);
returnn ewHead;
}
void quickSort(struct node **headRef)
{
(*headRef) = quickSortRecur(*headRef, getTail(*headRef));
return;
} |
|