微软等数据结构与算法面试100题第五题

第五题
查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

分析：本题目要求计算n个整数的最小的K个，题目没有直接给出复杂度的要求，因此有很多种解法。
比如排序后一次输出等很多种解法。如果是要求复杂度为klogn的话比较容易想到可以使用分治（递归）算法。

在这里我们使用了两种方法，第一个是比较经典的最小堆算法，第二种就是分治算法。在这里需要说明的一点就是其实这两种算法的本质是一样的，应该都可以算是递归或者分治。只是实现的时候表达出来不一样罢了。

最小堆代码：
[cpp]
#include<iostream>

using namespace std;

class minHeap{
private:
    int size;
    int * data;
    int currentSize;


    int Parent(int pos) const;//不会改变成员变量的值

public:
    minHeap(int size =100);
    ~minHeap(){delete [] data;}
    bool Insert(const int node);
    void siftUp(int pos);
    void siftDown();//放入左子树中
    int removeMin();

};

int minHeap::Parent(int pos) const
{
    return (pos-1)/2;
}
minHeap::minHeap(const int size)
{
    if(size<0)
        return;
    data = new int [size];
    currentSize = 0;
}

bool minHeap::Insert(const int node)
{
    if(currentSize < size-1)
        return false;
    else{
        data[currentSize] = node;
        siftUp(currentSize);
        currentSize = currentSize + 1;
        return true;
    }
}

void minHeap::siftUp(int pos)
{
    int temp;
    while(pos>0 && data[pos]<data[Parent(pos)])
    {
        temp = data[pos];
        data[pos] = data[Parent(pos)];
        data[Parent(pos)] = temp;

        pos = Parent(pos);
    }

}

void minHeap::siftDown()
{
    //默认从0位置开始下降，放进左子树

    int temp;
    //交换到末位
    temp = data[0];
    data[0] = data[currentSize-1];
    data[currentSize-1] = temp;

    currentSize = currentSize -1;

    int i = 0;
    while(i*2+1<=currentSize-1 && (data[i] > data[2*i+1] || data[i] > data[2*i+2])) //存在左右子树
    {

        if(i*2+2<=currentSize-1){
        //如果左右子树都有
            if(data[2*i+1] < data[2*i+2])
            {
                temp = data[i];
                data[i] = data[2*i+1];
                data[2*i+1] = temp;
                i = 2 * i + 1;
            }
            else
            {
                temp = data[i];
                data[i] = data[2*i+2];
                data[2*i+2] = temp;
                i = 2 * i + 2;
            }
        }
        else if (data[i] > data[2*i+1])
        {
            //如果只有左子树
            temp = data[i];
            data[i] = data[2*i+1];
            data[2*i+1] = temp;
            i = 2 * i + 1;
        }
        else
        {
            i = 2 * i + 1;
        }
    }


}

int minHeap::removeMin()
{
    int minValue = data[0];
    siftDown();

    return minValue;
}
int main()
{
    minHeap b;
    int a[] = { 2, 3, 4, 5, 7, 1, 9};
    for(int i = 0; i < sizeof(a)/ sizeof(int) ; i++)
        b.Insert(a[i]);
    for(int i = 0; i < sizeof(a)/ sizeof(int) ; i++)
        cout<<b.removeMin()<<endl;
    return 0;
}

递归代码（最大）：
[cpp]
#include<iostream>

using namespace std;

void maxHeap(int *a, int length, int index)
{
    int temp;
    //没有子树
    if(index*2+1>length-1){ }
    //只有左子树
    else if(index*2+1==length-1)
    {
&

补充：软件开发 , C++ ,

微软等数据结构与算法面试100题 第五题

微软等数据结构与算法面试100题第五题