求一個無序數組中第k小的數字

算法思想找一個點然後放到末尾然後將小於這個數的值放在數組前面大於這個值的放在數組後面然後在將這個末尾的數放回這個末尾數放入的位置i代表已經找到第i小的數放入的位置如果是k就找到了第k小的數

同樣找到第k大的數類似的解法找到前k個最大數也一樣找一個數組的中位數也一樣做求n個數組的中位數也一樣的做求n個數組的前k個大數或小數也類似可以做

代碼

//?swap?two?number

void?swap(int?&i?int?&j)

{

int?temp?=?i;

i?=?j;

j?=?temp;

}

//?find?a?position?to?partition?the?array

int?partition(int?start?int?end)

{

return?end/+start/;

}

//?quick?sort

int?QuickSort(int?a[]int?start?int?end)

{

if(start?>?end)

{

throw?&#;error&#;;

}

if(start?==?end)

{

return?end;

}

int?p?=?partition(startend);

int?i?=;

swap(a[p]a[end]);

int?j?=?end;

while(j>=i)

{

while(a[i]<a[end])

{

i++;

}

while(j?>=??&&?a[j]>a[end])

{

j&#;;

}

swap(a[i]a[j]);

}

swap(a[i]a[j]);

swap(a[i]a[end]);

return?i;

}

//?find?the?kth?smaller?number

int?FindK(int?a[]?int?numint?kth)

{

if(kth?>?num?||?kth?<=?)

{

throw?&#;error:?no?such?kth?number&#;;

}

int?k?=?kth;//?because?the?array?index?starts?with??not?;

int?position=?;

int?start?=?;

int?end?=?num;

while(position?!=?k)

{

position?=?QuickSort(astartend);

if(position?<?k)

{

start?=?position+;

}

else

{

end?=?position;

}

}

return?a[position];

}

/***************************************
輸入: ? 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)

From:http://tw.wingwit.com/Article/program/sjjg/201405/30745.html