求一个无序数组中第k小的数字

算法思想找一个点然后放到末尾然后将小于这个数的值放在数组前面大于这个值的放在数组后面然后在将这个末尾的数放回这个末尾数放入的位置i代表已经找到第i小的数放入的位置如果是k就找到了第k小的数

同样找到第k大的数类似的解法找到前k个最大数也一样找一个数组的中位数也一样做求n个数组的中位数也一样的做求n个数组的前k个大数或小数也类似可以做

代码

/***************************************
输入: ? n:数组元素的个数 ? k:第几大的数
a:待查找的数组元素
****************************************/
#include ? <stdioh>
#include ? <stdlibh>
#include ? <timeh>

#define ? N ?

void ? Rand_select( ? int* ? int ? int ? );
int ? partition( ? int* ? int ? int ? );
int ? swap( ? int& ? int& ? );
int ? k ? ans;

int ? main()
{
int ? n ? a[N] ? i;
while( ? scanf( ? &#;%d%d&#; ? &n ? &k ? ) ? != ? EOF ? )
{
srand(time(NULL));
k&#;;
for( ? i ? = ? ; ? i ? < ? n; ? i++ ? )
scanf( ? &#;%d&#; ? a ? + ? i ? );
Rand_select( ? a ? ? n ? );
printf( ? &#;%d\n&#; ? ans ? );
}
return ? ;
}

void ? Rand_select( ? int ? a[] ? int ? p ? int ? q ? )
{
int ? m;
if ? (p ? <= ? q)
{
m ? = ? partition( ? a ? p ? q ? );
if( ? k ? == ? m ? )
{ ? ? ? ? ? ? ans ? = ? a[m]; ? ? ? ? ? return; ? ? ? ? ? ? ? }
else ? if( ? k ? > ? m ? )
Rand_select( ? a ? m+ ? q ? );
else
Rand_select( ? a ? p ? m ? );
}
}

int ? partition( ? int ? a[] ? int ? p ? int ? q ? )
{
int ? last ? i;
if( ? q ? != ? p ? )
swap( ? a[rand()%(qp)+p] ? a[p] ? );
for( ? i ? = ? p+ ? last ? = ? p; ? i ? <= ? q; ? i++ ? )
if( ? a[i] ? >= ? a[p] ? )
swap( ? a[i] ? a[++last] ? );
swap( ? a[last] ? a[p] ? );
return ? last;
}

int ? swap( ? int ? &p ? int ? &q ? )
{
int ? temp ? = ? p;
p ? = ? q;
q ? = ? temp;
return ? ;
}

#include <iostream>;
using namespace std;

void swap(int& a int& b)
{
int temp = a;
a = b;
b = temp;
}

int k_smallest(int k int a[] int left int right)
{
int pivot = a[right]; //the last item as pivot
int i = left;
int j = right;
for(;;)
{
for(; a[i]<pivot; i++);
for(; a[j]>;=pivot; j&#;);
if(i<j)
swap(a[i] a[j]);
else
break;
}
swap(a[i] a[right]);
//now i is the pivot index in the array
//ie a[i] is the (i+)th smallest item

if(k==ileft+)
return a[i];
else if(k < ileft+)? ? //target before pivot
return k_smallest(k a left i);
else? ?//target after pivot
return k_smallest((k(ileft+)) a i+ right);
}

//find the k_th smallest item in the array
int Kth_smallest(int k int a[] int size)
{
return k_smallest(k a size);
}

int main()
{
int a[] = { };

for(int i=; i<=; i++)
cout<<Kth_smallest(i a )<<&#; &#;;
}

【转自】foxhaw/blog/cns!bcbdc!entry

int MaxK(int* data size_t len int k)//类似快排的思想
{
int *source = data;
while(true)
{
int l = source[];
int left = ;
int right = len &#; ;
while(left != right)
{
while((l > source[left]) && (right > left))left++;
while((l < source[right]) && (right > left))right&#;;
swap(source left right);
}
if(left == k &#; )
return max(source[] source[left]);
else if(left > k &#; )
{
if(source[] > source[left])
swap(source left );
//return MaxK(source left k);
len = left;
}
else
{
//return MaxK(source+left len &#; left k &#; left );
source += left;
len = len &#; left;
k = k &#; left;
}
}

return ;
}

int heapsort(int *data int n int bigk)//利用堆排序存在一种优化方案建立K大的堆
{
int data[] = {};
//Part
int i j j k;
int tmp;

for(k = (n>>) &#; ; k >= ; k&#;)
{
tmp = data[k];

for(j = k; (j<<) <= n; j = i)
{
j = j << ;
if(j+ > n)
i = j + ;
else
{
if(data[j+] < data[j+])
i = j+;
else
i = j+;
}

? if(tmp < data[i])
data[j] = data[i];
else
break;
}
data[j] = tmp;
}

//Part
int range = n &#; bigk;
for(k = n; k > range ; k&#;)
{
tmp = data[k];
data[k] = data[];
for(j = ; (j<<) <= k; j = i)
{
j = j<<;
if(j+ > k)
i = j+;
else
{
if(data[j+] < data[j+])
i = j+;
else
i = j+;
}
if(tmp < data[i])
data[j] = data[i];
else break;
}
data[j] = tmp;
}
return data[range];
}

int nthstl(int* source size_t len int k)//利用STL库中的方案
{
typedef vector<int> IntVector ;

? //Define an iterator for template class vector of strings
typedef IntVector::iterator IntVectorIt ;

? IntVector Numbers(len) ;
for(int i = ; i < len; i++)
{
Numbers[i] = source[i];
}
IntVectorIt start end it ;

? start = Numbersbegin() ;
end = Numbersend() ;

? nth_element(start start+k end) ;

return Numbers[k];
}

int stlk(int* source size_t len int k)//利用STL库中的方案即建立K大的堆

{
typedef vector<int> IntVector ;

? //Define an iterator for template class vector of strings
typedef IntVector::iterator IntVectorIt ;

? IntVector Numbers(len) ;
for(int i = ; i < len; i++)
{
Numbers[i] = source[i];
}
IntVectorIt start end it ;

? start = Numbersbegin() ;
end = Numbersend() ;

? partial_sort(start start+k end) ;

return Numbers[k];
}

可以先用快速排序进行排序其中用另外一个进行地址查找
代码如下在VC++运行通过给分吧^^

//快速排序

#include <iostream>

using namespace std;

int Partition ? (int *Lint lowint ? high)
{
int temp ? = ? L[low];
int pt ? = ? L[low];

while ? (low ? < ? high)
{
while ? (low ? < ? high ? && ? L[high] ? >= ? pt)
&#;high;
L[low] ? = ? L[high];
while ? (low ? < ? high ? && ? L[low] ? <= ? pt)
++low;
L[low] ? = ? temp;
}
L[low] ? = ? temp;

return low;
}

void QSort ? (int *Lint lowint ? high)
{
if ? (low ? < ? high)
{
int pl ? = ? Partition ? (Llowhigh);

QSort ? (Llowpl ? &#; ? );
QSort ? (Lpl ? + ? high);
}
}

int main ? ()
{
int narry[]addr[];
int sum ? = ? t;

cout ? << ? &#;Input ? number:&#; ? << ? endl;
cin ? >> ? t;

while ? (t ? != ? )
{
narry[sum] ? = ? t;
addr[sum ? ? ] ? = ? t;
sum++;

cin ? >> ? t;
}

sum ? = ? ;
QSort ? (narrysum);

for ? (int ? i ? = ? ; ? i ? <= ? sum;i++)
cout ? << ? narry[i] ? << ? &#;\t&#;;
cout ? << ? endl;

int k;
cout ? << ? &#;Please ? input ? place ? you ? want:&#; ? << ? endl;
cin ? >> ? k;

int aa ? = ? ;
int kk ? = ? ;
for ? (;;)
{
if ? (aa ? == ? k)
break;
if ? (narry[kk] ? != ? narry[kk ? + ? ])
{
aa ? += ? ;
kk++;
}

}

cout ? << ? &#;The ? NO&#; ? << ? k ? << ? &#;number ? is:&#; ? << ? narry[sum ? ? kk] ? << ? endl;
cout ? << ? &#;And ? it&#;s ? place ? is:&#; ? ;
for ? (i ? = ? ;i ? < ? sum;i++)
{
if ? (addr[i] ? == ? narry[sum ? ? kk])
cout ? << ? i ? << ? &#;\t&#;;
}

return ;
}

这道题去年baidu笔试也出现过当时写的是这个答案高手分析下
#include ? <mathh>
#include ? <timeh>
#include ? <string>
#include ? <iostream>
#include ? <vector>
using ? namespace ? std;

#define ? n ?
#define ? k ?

int ? main(int ? argc ? char* ? argv[])
{
srand((unsigned ? )time(NULL));
if ? ( ? k ? > ? n ? )
{
cout ? << ? &#;error!&#; ? << ? endl;
return ? ;
}
vector<int> ? src;
cout ? << ? &#;源&#; ? << ? n ? << ? &#;个数据如下&#; ? << ? endl;
for ? ( ? int ? i ? = ? ; ? i ? < ? n; ? i++ ? )
{
srcpush_back( ? rand() ? );
cout ? << ? src[i] ? << ? &#; ? &#;;
}
vector<int> ? maxNum; //顺序存入最大k个数第一个为最大的最后一个为第k大
for ? ( ? i ? = ? ; ? i ? < ? k; ? i++ ? )
{
maxNumpush_back(); //初始化maxNumk个
}
for ? ( ? i ? = ? ; ? i ? < ? n; ? i++ ? )
{
for ? ( ? int ? j ? = ? ; ? j ? < ? maxNumsize(); ? j++ ? )
{
if ? ( ? src[i] ? >= ? maxNum[j] ? ) //比当前的大则放入当前位置后面的数字依次后退
{
for ? ( ? int ? i ? = ? maxNumsize(); ? i ? > ? j; ? i&#; ? )
{
maxNum[i] ? = ? maxNum[i];
}
maxNum[j] ? = ? src[i];
break;
}
}
}
cout ? << ? endl ? << ? &#;第&#; ? << ? k ? << ? &#;大的数字为&#; ? << ? maxNum[k] ? << ? endl;
return ? ;
}
分析算法对n个数字只访问一次此部分的时间复杂度为O(n);但每访问一次须与k个数字分别比较所以总的时间渐复杂度为O(n*k)

上一篇：TFDN图片播放器 不错自动播放

下一篇：ubuntu12.04安装笔记