Chinaunix首页 | 论坛 | 博客
  • 博客访问: 495730
  • 博文数量: 80
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1916
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-11 22:01
个人简介

从事实时计算多年,熟悉jstorm/spark/flink/kafka/rocketMq, 热衷于开源,希望在这里和前辈们一起学习与分享,得到长足的进步!邮箱:hustfxj@gmail.com 我的githup地址是:https://github.com/hustfxj。欢迎和大家一起交流探讨问题。

文章分类

全部博文(80)

文章存档

2017年(11)

2015年(3)

2014年(33)

2013年(33)

分类: IT职场

2013-10-25 15:41:39

问题:

在O(N lgK) 时间内合并K个有序链表, 这里N指的是K个链表中所有的元素个数。

分析:

这是一道非常经典的面试题,在很多大公司的面试题中,此题频繁出现。这题也是算法导论的作业题。

这题的思路如下:

1) 在每一个链表中取出第一个值,然后把它们放在一个大小为K的数组里,然后把这个数组当成heap,然后把该堆建成最小堆。此步骤的时间复杂度为O(K)

2 )取出堆中的最小值(也是数组的第一个值),然后把该最小值所处的链表的下一个值放在数组的第一个位置。如果链表中有一个已经为空(元素已经都被取出),则改变heap的大小。然后,执行MIN-HEAPIFY操作,此步骤的时间复杂度为O(lg K).

3 ) 不断的重复步骤二,直到所有的链表都为空。

代码如下:

点击(此处)折叠或打开

  1. class ListNode {
  2.     int val;
  3.     ListNode next;
  4.     ListNode(int x) {
  5.         val = x;
  6.         next = null;
  7.     }
  8. }
  9.   
  10. public class Solution {
  11.     public static void main(String[] args) {
  12.             
  13.         ListNode n1 = new ListNode(1);
  14.         ListNode n7 = new ListNode(2);
  15.         ListNode n9 = new ListNode(2);
  16.         ListNode n2 = new ListNode(1);
  17.         ListNode n4 = new ListNode(1);
  18.         ListNode n8 = new ListNode(2);
  19.     
  20.         ArrayList<ListNode> lists = new ArrayList<ListNode>();    
  21.         n1.next = n7;
  22.         n7.next = n9;
  23.         n2.next = n4;
  24.         n4.next = n8;
  25.         
  26.         lists.add(n1);
  27.         lists.add(n2);
  28.         
  29.         Solution test = new Solution();
  30.         ListNode head = test.mergeKLists(lists);
  31.         while(head != null) {
  32.             System.out.println(head.val);
  33.             head = head.next;
  34.         }
  35.     }
  36.     
  37.     public ListNode mergeKLists(ArrayList<ListNode> lists) {
  38.         ArrayList<ListNode> heap = new ArrayList<ListNode>();
  39.         for (int i = 0; i < lists.size(); i++) {
  40.             if (lists.get(i) != null) {
  41.                 heap.add(lists.get(i));
  42.             }
  43.         }
  44.         
  45.         ListNode head = null;
  46.         ListNode current = null;
  47.         if (heap.size() == 0) return null;
  48.         minHeapify(heap);
  49.         while (heap.size() != 0) {
  50.             if (head == null) {
  51.                 head = heap.get(0);
  52.                 current = heap.get(0);
  53.             } else {
  54.                 current.next = heap.get(0);
  55.                 current = current.next;
  56.             }
  57.             
  58.             if (current.next != null) {
  59.                 heap.set(0, current.next);
  60.                 heapify(heap, 0);
  61.             } else {
  62.                 heap.remove(0);
  63.                 minHeapify(heap);
  64.             }
  65.         }
  66.         return head;
  67.     }
  68.     
  69.     public void heapify(ArrayList<ListNode> heap, int index) {
  70.         int position = index;
  71.         int left = 2 * index + 1;
  72.         int right = 2 * index + 2;
  73.         
  74.         if(left < heap.size() && heap.get(left).val < heap.get(position).val) {
  75.             position = left;
  76.         }
  77.         
  78.         if(right < heap.size() && heap.get(right).val < heap.get(position).val) {
  79.             position = right;
  80.         }
  81.         
  82.         if (position != index) {
  83.             ListNode temp = heap.get(position);
  84.             heap.set(position, heap.get(index));
  85.             heap.set(index, temp);
  86.             heapify(heap, position);
  87.         }
  88.     }
  89.     
  90.     public void minHeapify(ArrayList<ListNode> heap) {
  91.         for (int i = heap.size()/2 - 1; i >= 0; i--) {
  92.             heapify(heap, i);
  93.         }
  94.     }
  95. }

阅读(2250) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~