寻找序列中最小的第N个元素(partition函数实现)

时间:2022-04-14 23:13:08

Partition为分割算法,用于将一个序列a[n]分为三部分:a[n]中大于某一元素x的部分,等于x的部分和小于x的部分。

Partition程序如下:

long Partition (long a[], long p1, long p2)
{//对a[p1]~a[p2]进行分割,返回分割点的序号, p1, p2分别为元组的第一 //个和最后一个元素
long i, j;
int x;
i = p1;
j = p2;
x = a[i];
while (i<j)
{while ( a[j] >= x && i,j) j--;
if (i<j) {a[i] = a[j]; i++;}
while (a[i] <= x && i<j) i++;
if (i<j) {a [j] = a[i]; j--;}
} a[i] = x;
return i;
}

则利用partition 函数来实现查找第n个元素的程序如下所示:

long OrderStatistics(long a[], long p1, long p2, long k)
{// 在a[p1]~a[p2] 中, 找出最小值,并返回值
long p, num;
if (k< || k>p2-p1+) return -;
if (p1 >= p2) return a[p1];
//若a[p1]~a[p2] 只有一个元素,则返回该元素
p = Partition(a, p1, p2);
num = p-p1;
if (k == num + ) return a[p]; //第k小元素为分割点
if (k <= num) return OrderStatistics(a, p1, p-, k); //第k小元素在前部
return OrderStatistics(a, p+, p2, k-num-); // 第k 小元素在后部
}

Python cookbook 中给出了这一方法的python 实现, 如下所示:

import random

def select(data, n):
# 创建一个新列表, 处理小于0的索引, 检查索引的有效性
data = list(data)
if n<0:
n += len(data)
if not 0 <= n < len(data):
raise ValueError, "can't get rank %d out of %d" %(n, len(data))
# 主循环, 看上去类似于排序但不需要递归
while True:
pivot = random.choice(data)
pcount = 0
under, over = [], []
uappend, oappend = under.append, over.append
for elem in data:
if elem < pivot:
uappend(elem)
elif elem > pivot:
oappend(elem)
else:
pcount += 1
numunder = len(under)
if n < numunder:
data = under
elif n < numunder + pcount:
return pivot
else:
data = over
n -= numunder +pcount

作者提到,也可以通过下面的简单方法实现第k个元素的查找:

def selsor(data, n):
data = list(data)
data.sort()
return data[n]

以上两种方法都可以实现,但是“基于列表的sort方法的实现的确简单的多, 实现select也确实需要多付出一点力气, 但如果n足够大而且比较操作的开销也无法忽略的话,select就体现出它的价值了。”

寻找序列中最小的第N个元素(partition函数实现)的更多相关文章

  1. Find Min In Rotated Sorted Array,寻找反转序列中最小的元素。

    问题描述:寻找反转序列中最小的元素. 算法分析:和寻找某个数是一个道理,还是利用二分查找,总体上分两种情况.nums[left]<=nums[mid],else.但是,在截取子序列的时候,有可能 ...

  2. 寻找数组中的第K大的元素,多种解法以及分析

    遇到了一个很简单而有意思的问题,可以看出不同的算法策略对这个问题求解的优化过程.问题:寻找数组中的第K大的元素. 最简单的想法是直接进行排序,算法复杂度是O(N*logN).这么做很明显比较低效率,因 ...

  3. 窥探算法之美妙——寻找数组中最小的K个数&amp&semi;python中巧用最大堆

    原文发表在我的博客主页,转载请注明出处 前言 不论是小算法或者大系统,堆一直是某种场景下程序员比较亲睐的数据结构,而在python中,由于数据结构的极其灵活性,list,tuple, dict在很多情 ...

  4. 顺序统计:寻找序列中第k小的数

    最直观的解法,排序之后取下标为k的值即可. 但是此处采取的方法为类似快速排序分块的方法,利用一个支点将序列分为两个子序列(支点左边的值小于支点的值,支点右边大于等于支点的值). 如果支点下标等于k,则 ...

  5. 给一个由n-1个整数组成的未排序的序列,其元素都是1~n中的不同的整数。如何在线性时间复杂度内寻找序列中缺失的整数

    思路分析:尼玛这不就是等差数列么.首先将该n-1个整数相加,得到sum,然后用(1+n)n/2减去sum,得到的差即为缺失的整数.因为1~n一共n个数,n个数的和为(1+n)n/2,而未排序数列的和为 ...

  6. 在线性级别时间内找出无序序列中的第k个元素

    在一个无序序列中找出第k个元素,对于k很小或者很大时可以采取特殊的方法,比如用堆排序来实现 .但是对于与序列长度N成正比的k来说,就不是一件容易的事了,可能最容易想到的就是先将无序序列排序再遍历即可找 ...

  7. 计算序列中第k小的数

    作者:jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4046399.html 使用分治算法,首先选择随机选择轴值pivot,并使的序列中比pivot ...

  8. 利用Manacher算法寻找字符串中的最长回文序列(palindrome)

    寻找字符串中的最长回文序列和所有回文序列(正向和反向一样的序列,如aba,abba等)算是挺早以前提出的算法问题了,最近再刷Leetcode算法题的时候遇到了一个(题目),所以就顺便写下. 如果用正反 ...

  9. Openjudge计算概论-求序列中的众数

    /*===================================== 求序列中的众数 总时间限制: 1000ms 内存限制: 65536kB 描述 输入一个长度为N的整数序列 (不多于128 ...

随机推荐

  1. Socket之TCP连接&lowbar;TcpNoDelay

    摘自: http://jerrypeng.me/2013/08/mythical-40ms-delay-and-tcp-nodelay/

  2. AFNetworking&lpar;AFN&rpar;总结

    AFNetworking(AFN) ----主要做下载上传之用 //他是干啥的?发送请求,主要做下载上传之用 (苹果自带有获取服务器数据的方法NSURLConnection send,AFNetwor ...

  3. 为什么匿名内部类只能访问其所在方法中的final类型的局部变量?

    大部分时候,类被定义成一个独立的程序单元.在某些情况下,也会把一个类放在另一个类的内部定义,这个定义在其他类内部的类就被称为内部类,包含内部类的类也被称为外部类. class Outer { priv ...

  4. 如何修正导入模型的旋转&quest; How do I fix the rotation of an imported model&quest;

    原地址:http://game.ceeger.com/Manual/HOWTO-FixZAxisIsUp.html Some 3D art packages export their models s ...

  5. JUnit4的使用

    JUnit4是JUnit框架有史以来的最大改进,其主要目标便是利用Java5的Annotation特性简化测试用例的编写. 先简单解释一下什么是Annotation,这个单词一般是翻译成元数据.元数据 ...

  6. ubuntu下编译安装PHP

    首先配置configure // ./configure --prefix=/usr/local/php5 --with-apxs2=/usr/local/apache2/bin/apxs --wit ...

  7. hdu-5009-Paint Pearls-dp

    由题意我们能够知道,花费最多为n. 所以单次最多涂掉sqrt(n)种颜色. dp[i]:涂到第i个位置.之前的花费最少为多少. biao[i][j]:在第i个位置,往前涂j-1种颜色,涂到哪个位置. ...

  8. 使用Recovery Services备份文件及文件夹

    1.创建恢复服务保管库 2.在backup项中选择本地,备份文件和文件夹选项 3.根据提示下载Agent及保管库凭据 4.在文件服务器上安装Agent 5.选择"继续注册"项,并添 ...

  9. 1077 Eight

    Eight Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 37738   Accepted: 15932   Special ...

  10. idea取消double shift全局搜索

    一是因为它和输入法经常冲突,二来是因为它完全可以被其它的快捷键代替,如Ctrl+n,ctrl+shift+n,ctrl+shift+f之类的: 取消的方法,按ctrl+shift+a,然后输入regi ...