首页 > 代码库 > Kmin

Kmin

2024-07-06 11:29:35   216人阅读

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


联系
我们