今日面试题:

一个很大的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;
}

本文来自微信:待字闺中,2013-07-09发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。