題目描述：輸入n個(gè)整數(shù)，找出其中最小的k個(gè)數(shù)，例如，輸入{4,5,1,6,2,7,3,8}這8個(gè)數(shù)字，最小的4個(gè)數(shù)字是1,2,3,4

題目分析：首先我能想到的是先對數(shù)組排序，從小到大，然后直接輸出想要的最小的k個(gè)點(diǎn)，而根據(jù)排序算法，表現(xiàn)的比較好的快速排序時(shí)間復(fù)雜度為o(nlogn)，但是有沒有時(shí)間復(fù)雜度更小的呢？在快速排序中，我們寫過一個(gè)partition函數(shù)，它的作用是將比基準(zhǔn)值小的放到數(shù)組前面，大的放到數(shù)組后面，如果小的那部分長度不滿足我們要求的k值，我們通過左移或者右移知道找到我們想要的k值，代碼如下：

#include<iostream>
using namespace std;

int pa(int* input, int start, int end) {
    int begin = start;//快排函數(shù)將數(shù)組比一個(gè)值小的值放到數(shù)組前面，大的放后面
    int last = end;
    int key = input[begin];
    while (begin < last) {
        while (begin < last&&input[last] >= key) {
            last--;
        }
        input[begin] = input[last];
        while (begin < last&&input[begin] <= key) {
            begin++;
        }
        input[last] = input[begin];
    }
    input[begin] = key;
    return begin;
}

int *GetKLeastNum(int* input, int n, int k) {
    if (input == nullptr || k > n || n <= 0 || k <= 0) {
        return 0;
    }
    int start = 0;
    int end = n - 1;
    int index = pa(input, start, end);
    while (index != k - 1) {
        if (index > k - 1) {
            end = index - 1;
            index = pa(input, start, end);
        }
        else {
            start = index + 1;
            index = pa(input, start, end);
        }//如果快排基準(zhǔn)值前面值數(shù)量小于k，那么在后面接著找基準(zhǔn)值，否則往前面找基準(zhǔn)值，直到找到前面有k個(gè)值的基準(zhǔn)值
    }
    return input;
}

int main() {
    int k = 4;
    int n = 8;
    int input[8] = { 4,5,1,6,2,7,3,8 };
    int *value;
    value = GetKLeastNum(input, n, k);
    for (int i = 0; i < k; ++i) {
        cout << value[i] << endl;
    }
}

但是這樣會(huì)改變數(shù)組位置，給原數(shù)組帶來變化，若實(shí)際情況不允許變動(dòng)，則需要重新選擇新的方法：

創(chuàng)建一個(gè)可以裝k個(gè)數(shù)的容器，輸入值首先裝滿容器，當(dāng)容器滿了后，新輸入的數(shù)與容器中的其他值比較，如果比最大值小，則最大值出容器，新來的值進(jìn)容器，對這個(gè)容器，我們有兩種想法，一個(gè)是最大堆，首先建立一個(gè)k個(gè)數(shù)的最大堆，每次拿一個(gè)數(shù)與堆頂元素比較，當(dāng)這個(gè)數(shù)比堆頂元素大時(shí)，與堆頂元素交換，然后調(diào)整重新得到一個(gè)最大堆，遍歷所有的數(shù)直到最小的k個(gè)值都進(jìn)堆中。

n個(gè)數(shù)組成的堆高度為o(logn)，和向量對應(yīng)起來，有三條性質(zhì)(根節(jié)點(diǎn)i(v)=0)：

a)若節(jié)點(diǎn)v有左孩子，那么編號i(LeftChild(v))=2*i(v)+1

b)若節(jié)點(diǎn)v有右孩子，那么編號i(RightChild(v))=2*i(v)+2，

c)若節(jié)點(diǎn)v有父節(jié)點(diǎn)，那么編號i(Parent(v))=ceil[i(v)/2]-1，(ceil表示上取整)

而最大堆性質(zhì)是任意節(jié)點(diǎn)值比它的子節(jié)點(diǎn)值都要大，最小堆是任意節(jié)點(diǎn)的值比它的子節(jié)點(diǎn)值都要小，通俗點(diǎn)理解就是最大堆從上到下任何一條路徑都是從大到小排序好的，最小堆從上到下任何一條路徑都是從小到大排序好的，找到前k個(gè)最小值代碼如下：

#include<iostream>
using namespace std;

void swap(int* x1,int* x2) {
    int temp = *x1;
    *x1 = *x2;
    *x2 = temp;
}

void AdjustDown(int* input,int k, int parent) {
    if (input == NULL || k <= 0) { return; }
    int child = 2 * parent + 1;
    while (child<k) {
        if ((child + 1 < k) && (input[child] < input[child + 1]))
            ++child;//左節(jié)點(diǎn)和右節(jié)點(diǎn)選最大的值往上檢索
        if (input[child] > input[parent]) {//從當(dāng)前往上排序直到堆頂
            swap(&input[child], &input[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
            break;
    }
}

int *GetKLeastNum(int* input, int n ,int k) {
    int i = 0;
    for (i = (2 * k - 2) / 2; i >= 0;--i) {
        AdjustDown(input, k, i);//選擇數(shù)組前k個(gè)值構(gòu)建一個(gè)最大堆
    }
    for (i = k; i < n;++i) {
        if (input[i]<input[0]) {//將后n-k個(gè)值一個(gè)個(gè)送入最大堆，小于最大值則最大值彈出，重新構(gòu)建最大堆
            swap(&input[i], &input[0]);
            AdjustDown(input, k, 0);
        }
    }    
    return input;
}

int main() {
    int k = 4;
    int n = 8;
    int input[8] = { 4,5,1,6,2,7,3,8 };    
    int *value;
    value = GetKLeastNum(input, n, k);
    for (int i = 0; i < k; ++i) {
        cout << value[i] << endl;
    }
}

另一種是紅黑二叉樹，紅黑二叉樹主要是對2-3查找樹進(jìn)行編碼，需要滿足以下條件：

(1)二叉樹樹根始終為黑色

(2)外部節(jié)點(diǎn)均為黑色

(3)如果節(jié)點(diǎn)為紅色，則子節(jié)點(diǎn)均為黑色

(4)從任何一個(gè)外部節(jié)點(diǎn)到根節(jié)點(diǎn)的沿途，黑色節(jié)點(diǎn)數(shù)目相等

紅黑樹理解起來頗為復(fù)雜，等待后續(xù)更新

參考：

http://www.cnblogs.com/skywang12345/p/3610187.html(堆與二叉堆基礎(chǔ)知識)

https://blog.csdn.net/pursue_my_life/article/details/80253469(堆的構(gòu)建以及堆排序)

https://www.cnblogs.com/edisonchou/p/4799678.html(對應(yīng)本題最大堆及測試方法)

總結(jié)

以上是生活随笔為你收集整理的剑指offer自学系列(一)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。