时间:2021-05-19
求数组中第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;
}
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法。分享给大家供大家参考,具体如下:题目:是在一组数组(数组元素为整数,可正可负可为0)中查找乘积最大的
本文实例讲述了Java均摊复杂度和防止复杂度的震荡。分享给大家供大家参考,具体如下:关于上一节封装数组的简单复杂度分析方法中我们对添加操作的时间复杂度归结为O(
算法的平均时间复杂度为O(nlogn)。但是当输入是已经排序的数组或几乎排好序的输入,时间复杂度却为O(n^2)。为解决这一问题并保证平均时间复杂度为O(nlo
本文实例讲述了Java针对封装数组的简单复杂度分析方法。分享给大家供大家参考,具体如下:完成了数组的封装之后我们还需对其进行复杂度分析:此处的复杂度分析主要是指
在实现算法的时候,通常会从两方面考虑算法的复杂度,即时间复杂度和空间复杂度。顾名思义,时间复杂度用于度量算法的计算工作量,空间复杂度用于度量算法占用的内存空间。