MapReduce矩阵；及快排单链表之解答

今日面试题：

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

文章标题：MapReduce矩阵；及快排单链表之解答
文章转载：http://www.csdahua.cn/qtweb/news24/452474.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网