`
wangleide414
  • 浏览: 606682 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

查找第K小的元素的O(N)算法

 
阅读更多

话说这个问题,比较挫的解决方案有

1.先排序,然后找到第K小的,复杂度是O(nlogn)

2.选择排序来搞,选择排序是O(kn),

3.堆排序是O(nlogk)

4.比较好的解决方案是利用类似快速排序的划分思想来找到第K小,复杂度为O(n),但是最坏情况可能达到O(n^2)

5.还有种方法可以使得最坏情况也是O(n)。


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

 

  1. import random

  2.  

  3. def partition(arr, left, right, pivot):

  4.     v = arr[pivot]

  5.     arr[pivot], arr[right-1] = arr[right-1], arr[pivot]

  6.     index = left

  7.     for i in xrange(left, right):

  8.         if arr[i] <= v:

  9.             arr[i], arr[index] = arr[index], arr[i]

  10.             index += 1

  11.     return index-1

  12.  

  13. def select(arr, left, right, k):

  14.     while right - left > 1:

  15.         index = partition(arr, left, right, random.randint(left, right-1))

  16.         dist = index - left + 1

  17.         if dist == k:

  18.             return arr[index]

  19.         if dist < k:

  20.             k -= dist

  21.             left = index + 1

  22.         else:

  23.             right = index

  24.     return arr[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/5)+T(7/10*n)+O(n)<=c*n*(1+9/10+(9/10)^2....) 
所以T(n)=O(n)

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

 

  1. import heapq

  2.  

  3. def partition(arr, left, right, pivot):

  4.     v = arr[pivot]

  5.     arr[pivot], arr[right-1] = arr[right-1], arr[pivot]

  6.     index = left

  7.     for i in xrange(left, right):

  8.         if arr[i] <= v:

  9.             arr[i], arr[index] = arr[index], arr[i]

  10.             index += 1

  11.     return index-1

  12.  

  13. def select_heap(arr, left, right, k):

  14.     tmp = arr[left:right]

  15.     heapq.heapify(tmp)

  16.     [heapq.heappop(tmp) for i in xrange(k-1)]

  17.     return heapq.heappop(tmp)

  18.  

  19. def median(arr, left, right):

  20.     num = (right - left - 1) / 5

  21.     for i in xrange(num+1):

  22.         sub_left = left + i*5

  23.         sub_right = sub_left + 5

  24.         if sub_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.     return select(arr, left, left+num+1, (num+1)/2)

  29.  

  30. def select(arr, left, right, k):

  31.     while right - left > 1:

  32.         pivot = median(arr, left, right)

  33.         index = partition(arr, left, right, pivot)

  34.         dist = index - left + 1

  35.         if dist == k:

  36.             return arr[index]

  37.         if dist < k:

  38.             k -= dist

  39.             left = index + 1

  40.         else:

  41.             right = index

  42.     return arr[left]

 

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

分享到:
评论

相关推荐

    寻找第k小元素 基本算法复习

    在计算机科学和编程领域,寻找第k小元素是一项常见的任务,它涉及到排序和搜索算法的知识。这个主题是对基本算法的复习,旨在强化我们对高效解决问题的理解。在此,我们将深入探讨几种寻找第k小元素的算法,并分析...

    算法:求第k小元素

    在计算机科学中,"求第k小元素"是算法设计中的一个重要问题,它涉及到排序和查找的技巧。这个问题的目标是从一个未排序或者部分排序的数组或集合中找到第k个最小的元素,其中k通常是一个正整数。这个问题在数据分析...

    第k小元素查找C++程序实现

    在计算机科学中,查找第k小元素是常见的算法问题,特别是在数据结构和算法设计中。这个问题的基本目标是从一个未排序或已排序的数组或集合中找出第k个最小的元素。这里我们将深入探讨三种方法来解决这个问题:中位...

    算法中最小K元素的选择问题

    在计算机科学中,"算法中最小K元素的选择问题"是一个重要的数据结构和算法主题,它涉及到从一个无序或有序的数组中找到第K小(或大)的元素。这个问题在各种应用场景中都有广泛的应用,比如数据库查询优化、排序算法...

    第k小元素 算法分析与设计 四种算法实现

    - **缺点**:最坏情况下时间复杂度为O(n^2),但这种情况在寻找第k小元素时不太可能出现。 3. **中位数法**: - **概念**:中位数法是通过寻找数组的中位数来划分数据,使得划分后的两部分大小大致相等,进一步...

    查找第k小2_K._查找第k小_

    4. **线性时间复杂度的解决方案**:例如,快速选择的Lomuto分区方案和Hoare分区方案,或者使用随机化算法如median-of-medians方法,这些可以在平均时间复杂度为O(n)的情况下找到第k小的元素,但最坏情况下的时间...

    查找第K小的元素2

    3. **线性时间复杂度的解决方案**:例如,可以使用“快速选择”算法,它是快速排序的一个变种,专门用于查找第K小的元素,其平均时间复杂度为O(n)。 4. **平衡分割**:在划分数组时,尽量使两个子数组的大小相近,...

    一个在有序行和列的矩阵中选择第k小元素的O(n)时间复杂度算法

    本文主要讨论的是如何在这样一个矩阵中找到第k小的元素,而该问题的核心是一个O(n)时间复杂度的算法,这是由A. Mirzaian和E. Arjomandi在1985年的论文中提出的。 有序矩阵的选择问题可以视为一个经典的排序和搜索...

    快速排序求解数组第k小元素

    通过调整快速排序的逻辑,可以在O(n)的时间复杂度内找到第k小的元素。 1. **选取基准值**:通常情况下,可以选择数组的第一个元素作为基准值。 2. **划分数组**:将数组划分为两个子数组,一个包含所有小于基准值的...

    寻找第k小元素(vc)

    在编程领域,寻找第k小元素(或第k大元素)是常见的算法问题,它涉及到对数据集合的排序和查找。在这个问题中,我们要在数组中找到第k个最小的元素,同时考虑到数组中可能存在重复的元素。这个问题在实际应用中广泛...

    排序(下):如何用快排思想在O(n)内查找第K大元素?.pdf

    ### 如何用快排思想在O(n)内查找第K大元素? #### 一、引言 本篇文章探讨了一个有趣且实用的计算机科学问题:如何利用快速排序的思想,在线性时间内找出一个无序数组中的第K大元素。这个问题不仅考验着我们对数据...

    分治算法求最大值与最小值,找最小元素

    在本题中,我们关注的是如何运用分治算法来找到一组数字中的最大值和最小值,以及如何找出第k个最小元素。这两个问题都可以通过分治思想进行有效解决。 首先,寻找最大值和最小值。传统的做法是遍历整个数组,但...

    查找第i小的元素

    标题中的“查找第i小的元素”是指在一组无序数据中找到第i个最小的元素,例如在未排序的数组或集合中找到第k小的元素,这是一个常见的算法问题,广泛应用于各种数据结构和算法的实践中。这个问题的解决方法通常涉及...

    实验六寻找第k小的元素.doc

    实验六的目的是寻找数组中的第k...通过对数组的不断分割和定位,最终能够在线性时间内找到第k小的元素,体现了算法分析与设计的重要性。这种算法不仅在理论上有重要的意义,而且在实际编程和数据处理中也有广泛的应用。

    12排序(下):如何用快排思想在O(n)内查找第K大元素?.pdf

    快速排序算法也可以用来在O(n)的时间复杂度内查找无序数组中的第K大元素。快速选择算法是快速排序算法的一个变种,利用快速排序的思想,在数组中找到第K大的元素。快速选择算法的基本思想是,进行一次划分操作后,...

    求数列中的第1~k小元素

    给定文件中提到的“SELECT”算法是一种高效的查找数列中第k小元素的方法,其时间复杂度为O(n),在处理大数据量时尤其高效。算法的核心思想是利用分治策略,通过不断将数组分割成较小的部分来逐步逼近目标元素的位置...

    C++实现的O(n)复杂度内查找第K大数算法示例

    该算法可以应用于多种场景,例如在数据分析和机器学习等领域中查找Top-K元素。 通过实例分析,我们可以看到,该算法的实现过程非常复杂,需要对C++语言和算法有深入的了解。但是,该算法的应用前景非常广阔,可以在...

    查找第K小的元素 _ isnowfy1

    在算法领域,寻找第K小元素是一个常见的问题,它在数据结构和算法设计中具有重要地位。本问题探讨了多种解决方法,包括基于排序、选择排序、堆排序以及快速排序思想的优化策略。 首先,最基本的解决方案是通过排序...

    algo_third_第k小元素c++_

    然而,这个“algo_third_第k小元素c++”的描述中提到了一种改进的策略,它将元素划分为9个一组,目的是减少比较次数,从而降低时间复杂度到O(n)。 以下是这种策略的可能实现思路: 1. **分组策略**:首先,我们...

    选择第k小问题.zip

    对于寻找第k小元素的问题,我们可以使用“快速选择”算法,这是快速排序的一个变种,它的核心思想是利用分治法来减少查找范围。 以下是一种可能的实现过程: 1. **选取枢轴**:首先,从数组中随机选取一个元素作为...

Global site tag (gtag.js) - Google Analytics