首页 > 代码库 > Kmin

Kmin

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