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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

// 70_Kmin_of_Array_and_BST.cpp : Defines the entry point for the console application.
//
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/9/18
*/

#include "stdafx.h"
#include "iostream"
#include <ctime>
#include <algorithm>
using namespace std;

void print(int *a, int n)
{
    ; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

int compare_less (const void *a, const void *b)
{
    return ( *(int *)a - * (int *)b );
}

//========================================================
//   kmin of array
//========================================================
void myswap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}

int partition1(int *a, int left, int right)
{
    // a[left,...p-1]<=a[p]<a[p+1,...right]
    int i = left;
    int j = right;
    int key = a[left];
    while(i < j)
    {
        while(a[i] <= key) i++;
        while(a[j] > key) j--;
        if (i < j)
        {
            myswap(a[i], a[j]);
        }
    }
    // left---j---i---right
    myswap(a[left], a[j]);
    return j;
}

int kmin(int *a, int left, int right, int k)
{
    if(left < = right)
    {
        int p = partition1(a, left, right);
        ;
        if (k == pk)
        {
            return a[p];
        }
        else if (k < pk)
        {
            , k);
        }
        else // k >pk
        {
            , right, k - pk);
        }
    }
}

int Kmin_of_Array(int *a, int n, int k)
{
    )
        ;
     || k > n)
        ;
    , k);
}

void test_base(int *a, int n, int k)
{
    print(a, n);
    qsort(a, n, sizeof(int), compare_less);
    print(a, n);
    cout << k << " min of array is: " << Kmin_of_Array(a, n, k) << endl;
    cout << "==============================\n";
}

void test_default()
{
    srand((unsigned int)time(NULL));
    ;
    int a[n];
    ; i < n; i++)
    {
        a[i] = rand() % ;
    }
    test_base(a, n, );
}

void test_main()
{
    test_default();
}

int _tmain(int argc, _TCHAR *argv[])
{
    test_main();
    ;
}
/*
37 30 22 10 22 63 6 44 36 41 43 75 54 77 9 99 3 13 28 27
3 6 9 10 13 22 22 27 28 30 36 37 41 43 44 54 63 75 77 99
3 min of array is: 9
==============================
*/

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

//========================================================
//   kmin of bst
//========================================================
// binary tree node struct
struct BinaryTreeNode
{
    int value;
    BinaryTreeNode *parent; // for rank of bst
    BinaryTreeNode *left;
    BinaryTreeNode *right;
    int size; // for kmin of bst
    // x.size = x.left.size + x.right.size +1
};

int node_size(BinaryTreeNode *node)
{
    // get node size of node
    if (node == NULL)
        ;
    node->size = node_size(node->left) + node_size(node->right) + ;
    return node->size;
}

int left_size(BinaryTreeNode *node)
{
    // get left size of node in o(1)
;
}

BinaryTreeNode *kmin_bst(BinaryTreeNode *root, int k)
{
    if (root == NULL)
        return NULL;

; // get node rank first

if (k == pk)
    {
        return root;
    }
    else if (k < pk)
    {
        return kmin_bst(root->left, k);
    }
    else // k>pk
    {
        return kmin_bst(root->right, k - pk);
    }
}

BinaryTreeNode *Kmin_of_BST(BinaryTreeNode *root, int k)
{
    if (root == NULL)
        return NULL;
    // get node size of bst first
    int nodes = node_size(root);
     || k > nodes)
        return NULL;
    // use node size info to get kmin of bst
    return kmin_bst(root, k);
}