求数组中第K大的数可以基于快排序思想,步骤如下:
1、随机选择一个支点
2、将比支点大的数,放到数组左边;将比支点小的数放到数组右边;将支点放到中间(属于左部分)
3、设左部分的长度为L,
当K < L时,递归地在左部分找第K大的数
当K > L时,递归地在有部分中找第(K - L)大的数
当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数
以上思想的代码实现如下:
/**
线性时间复杂度求数组中第K大数
** author :liuzhiwei
** data :2011-08-07
**/
#include "iostream"
using namespace std;
//基于快速排序思想,求数组a中第k大的数,low和high分别为数组的起始和结束位置
//时间复杂度为o(n),n为数组的长度
//1<=k<=n
//如果存在,返回第k大数的下标,否则返回-1
int selectk(int a[], int low, int high, int k)
{
if(k <= 0)
return -1;
if(k > high - low + 1)
return -1;
int pivot = low + rand()%(high - low + 1); //随即选择一个支点
swap(a[low], a[pivot]);
int m = low;
int count = 1;
//一趟遍历,把较大的数放到数组的左边
for(int i = low + 1; i <= high; ++i)
{
if(a[i] > a[low])
{
swap(a[++m], a[i]);
count++; //比支点大的数的个数为count-1
}
}
swap(a[m], a[low]); //将支点放在左、右两部分的分界处
if(count > k)
{
return selectk(a, low, m - 1, k);
}
else if( count < k)
{
return selectk(a, m + 1, high, k - count);
}
else
{
return m;
}
}
int main(void)
{
int a[] = {5, 15, 5, 7, 9, 17,100, 3, 12, 10, 19, 18, 16, 10, 1000,1,1,1,1,1,1,1,1};
int r = selectk(a, 0, sizeof(a) /sizeof(int) - 1, 5);
cout<<(r == -1 ? r : a[r])<<endl;
system("pause");
return 0;
}
稍微改动一下,就可以修改为求数组中第K小数
完整的代码如下:
/**
线性时间复杂度求数组中第K小数
** author :liuzhiwei
** data :2011-08-07
**/
#include "iostream"
using namespace std;
//基于快速排序思想,求数组a中第k小的数,low和high分别为数组的起始和结束位置
//时间复杂度为o(n),n为数组的长度
//1<=k<=n
//如果存在,返回第k小数的下标,否则返回-1
int selectk(int a[], int low, int high, int k)
{
if(k <= 0)
return -1;
if(k > high - low + 1)
return -1;
int pivot = low + rand()%(high - low + 1); //随即选择一个支点
swap(a[low], a[pivot]);
int m = low;
int count = 1;
//一趟遍历,把较小的数放到数组的左边
for(int i = low + 1; i <= high; ++i)
{
if(a[i]<a[low])
{
swap(a[++m], a[i]);
count++; //比支点小的数的个数为count-1
}
}
swap(a[m], a[low]); //将支点放在左、右两部分的分界处
if(k < count)
{
return selectk(a, low, m - 1, k);
}
else if( k > count)
{
return selectk(a, m + 1, high, k - count);
}
else
{
return m;
}
}
int main(void)
{
int a[] = {5, 15, 5, 7, 9, 17,100, 3, 12, 10, 19, 18, 16, 10, 1000,1,1,1,1,1,1,1,1};
int r = selectk(a, 0, sizeof(a) /sizeof(int) - 1, 23);
cout<<(r == -1 ? r : a[r])<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
当K < L> L时,递归地在有部分中找第(K – L)大的数当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数以上思想的代码实现如下: 代码如下:/**线性时间复杂度求数组中第K大数** author :...
信息安全领域中,传统使用m序列为基序列,对序列进行非线性组合、非线性滤波和非均匀采样等产生线性复杂度很高的序列,其线性复杂度的稳定性却不如意。提出伪随机序列称为m子序列,m子序列通过改变m序列的状态转换次序而...
KMP算法,全称Knuth-Morris-Pratt字符串搜索算法,是一种线性时间复杂度的字符串匹配算法。它的主要思想是在发生不匹配时,能知道部分已经匹配的字符序列的后缀和模式串的前缀存在重复,因此可以利用这些信息避免...
主元素C程序,分析时间复杂度,包括线性情况,真的很好,真的很好
运用Chan-Games给出了当k=4或5时,F2上固定线性复杂度为2n-2m-1的2n-周期二元序列的k-错线性复杂度所有可能值,LCk(s)=0或LCk(s)=2n-2m-2r 1 c,LCk(s)=2n-2r 1 c。这一结果对流密码稳定性的研究有重要的应用...
BM算法,用于计算序列的线性复杂度及其反馈多项式。使用JAVA实现
线性复杂度和k-错线性复杂度是衡量密钥序列随机性的两个重要标准,运用Chan-Games算法,得到线性复杂度为2n-2m的2n-周期二元序列的k-错线性复杂度的所有可能的值,LCk(s)=0或2n-2m-2r 1 c,2n-2r 1 c。这一结果对于...
给定k-错线性复杂度的2_n-周期二元序列条数及Matlab程序
本文在研究Games—Chan算法的基础上,给出了周期为2“的二元序列k错线性复杂度的一个快速算法。新算法是对Stamp-Martin算法的改进,与Stamp—Martin算法相比更为简单和高效。
数组是由有限个相同类型的变量所组成的有序集合,它可以进行元素的插入、删除、查找等操作,它的物理存储方式是顺序存储,访问方式是随机访问,利用下标查找数组元素的时间复杂度O[1],中间插入,删除数组元素的时间...
线性结构和非线性结构、稀疏数组、队列、链表(LinkedList) 数组和链表.pdf
用c++实现的平均O(n)时间和最坏O(n)时间求数组中第i大的数
一类p元序列集的相关性和线性复杂度的分析pdf,一类p元序列集的相关性和线性复杂度的分析
题目给定了一个包含n个元素的一维线性序列a[0:14]={2,9,11,3,14,7,10,8,15,4,13,1,6,5,12},想要我们求第k小的元素。 注意看,a[0:14]是一个未排序好的数组!那么想要求第k小的元素,我们第一步要干啥?然后呢?...
综合线性复杂度、k错线性复杂度、k错线性复杂度曲线和最小错误minerror(S)的概念,提出紧错线性复杂度的概念。在GF(pm)上周期为pn序列的k错线性复杂度快速算法的基础上,给出m紧错线性复杂度的快速算法。其中p是素数...
将TXT文件中的数据读进二维数组,并对列数据进行线性插值再以txt文件将数据输出
可以处理无限数据,求其线性复杂度 //by史瑞 //LFSR线性移位寄存器以及求异或运算OK unsigned char LFSRB_M(unsigned char *fun,unsigned char *seq,unsigned long Cont){ unsigned long x; unsigned char ch=0x...
部分匹配表是一个数组,其构建方法如下:对于模式串中的每个前缀子串,找出最长的、同时也是后缀的子串(不包括整个前缀子串本身),记录这个最长后缀子串的长度。部分匹配表的每个元素对应模式串的一个位置,存储的...