CWYAlpha

Just another WordPress.com site

Thought this was cool: 查找第K小的元素

leave a comment »


感觉这是个经典问题了,但是今天看维基百科的时候还是有了新的发现,话说这个问题,比较挫的解决方案有先排序,然后找到第K小的,复杂度是O(nlogn),还有就是利用选择排序或者是堆排序来搞,选择排序是O(kn),堆排序是O(nlogk),比较好的解决方案是利用类似快速排序的思想来找到第K小,复杂度为O(n),但是最坏情况可能达到O(n^2),不过今天要说的,就是还有种方法可以使得最坏情况也是O(n)。

我们先来看用快速排序的思想来搞的方案。快速排序是找到一个数,然后把所有数分为小于等于那个数的一堆,和大于那个数的一堆,然后两段分别递归来排序,而我们查找算法里,由于知道第K小的元素会在哪一堆,这样只需要递归其中一对即可。

  1. importrandom
  2.  
  3. defpartition(arr, left, right, pivot):
  4.     v = arr[pivot]
  5.     arr[pivot], arr[right-1]= arr[right-1], arr[pivot]
  6.     index = left
  7.    foriinxrange(left, right):
  8.        ifarr[i]<= v:
  9.             arr[i], arr[index]= arr[index], arr[i]
  10.             index +=1
  11.    returnindex-1
  12.  
  13. defselect(arr, left, right, k):
  14.    whileright – left>1:
  15.         index = partition(arr, left, right,random.randint(left, right-1))
  16.         dist = index – left +1
  17.        ifdist == k:
  18.            returnarr[index]
  19.        ifdist<k:
  20.             k -= dist
  21.             left = index +1
  22.        else:
  23.             right = index
  24.    returnarr[left]

之后arr是要查找的数组,调用select即可找到第K小元素,如果pivot元素选的不好那么这个算法最坏的情况是O(n^2)。

现在讨论最坏情况下也是O(n)的方案,把所有的数分为5个一堆,那么总共会有n/5堆,对于每堆我们可以很快的找到中位数(因为只有5个所以很容易嘛),之后调用当前算法找到这n/5个中位数的中位数,用这个数来做pivot,所以这个算法被叫做Median of Medians algorithm。

把中位数的中位数作为pivot的话,那么原数组中便会有3/5*1/2个也就是3/10个小于等于这个pivot的,同理会有3/10大于这个pivot的,所以最坏情况下,数组被分为30%,70%或者70%,30%的两部分。

T(n) 所以T(n)=O(n)

也就是最坏情况下是O(n)。

  1. importheapq
  2.  
  3. defpartition(arr, left, right, pivot):
  4.     v = arr[pivot]
  5.     arr[pivot], arr[right-1]= arr[right-1], arr[pivot]
  6.     index = left
  7.    foriinxrange(left, right):
  8.        ifarr[i]<= v:
  9.             arr[i], arr[index]= arr[index], arr[i]
  10.             index +=1
  11.    returnindex-1
  12.  
  13. defselect_heap(arr, left, right, k):
  14.     tmp = arr[left:right]
  15.    heapq.heapify(tmp)
  16.    [heapq.heappop(tmp)foriinxrange(k-1)]
  17.    returnheapq.heappop(tmp)
  18.  
  19. defmedian(arr, left, right):
  20.     num =(right – left -1)/5
  21.    foriinxrange(num+1):
  22.         sub_left = left + i*5
  23.         sub_right = sub_left +5
  24.        ifsub_right>right:
  25.             sub_right = right
  26.         m_index = select_heap(arr, sub_left, sub_right,(sub_right-sub_left)/2)
  27.         arr[left+i], arr[m_index]= arr[m_index], arr[left+i]
  28.    returnselect(arr, left, left+num+1,(num+1)/2)
  29.  
  30. defselect(arr, left, right, k):
  31.    whileright – left>1:
  32.         pivot = median(arr, left, right)
  33.         index = partition(arr, left, right, pivot)
  34.         dist = index – left +1
  35.        ifdist == k:
  36.            returnarr[index]
  37.        ifdist<k:
  38.             k -= dist
  39.             left = index +1
  40.        else:
  41.             right = index
  42.    returnarr[left]

同理,如果快速排序每次选pivot时用Median of Medians algorithm也可以把最坏情况降低为O(nlogn)的。

我猜您可能还会喜欢:


0

   

1

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 1
|
10000+ 本编程/Linux PDF/CHM 电子书下载

from IT牛人博客聚合网站: http://www.udpwork.com/item/8039.html

Written by cwyalpha

九月 2, 2012 在 8:09 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: