Kmin of Array
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/kmin-of-array.html
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/30
*/
int Partition(int a[], int left, int right)
{
// partition so that a[left..p-1]<=a[p] and a[p+1..right]>a[p]
int pivot = a[left], i = left , j = right;
while (i < j)
{
while (a[i] <= pivot) i++;
while (a[j] > pivot) j--;
if (i < j)
myswap(a[i], a[j]);
}
myswap(a[left], a[j]);
return j;
}
int Kmin(int a[], int left, int right, int k)
{
// a[0..n-1], 1<=k<=n
if(left <= right) // less or equal
{
int p = Partition(a, left, right);
if(p < k - 1)
return Kmin(a, p + 1, right, k); // right search
else if(p > k - 1)
return Kmin(a, left, p - 1, k); // left search
else return a[p];
}
return NOT_FOUND;
}
int Kmin(int a[], int n, int k)
{
if (k < 1 || k > n)
return NOT_FOUND;
return Kmin(a, 0, n - 1, k);
}
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/kmin-of-array.html
