笔试算法题（03）：最小第K个数 & 判定BST后序序列

出题：输入N个整数，要求输出其中最小的K个数；

分析：

• 快速排序和最小堆都可以解决最小（大）K个数的问题（时间复杂度为O(NlogN)）；另外可以建立大小为K的最大堆，将前K个数不断插入最大堆，对于之后的N-K个数，依次与堆顶元素进行比较，如果新元素更小则删除当前堆顶元素，并更新最大堆；如果新元素大则跳过；
• 第一种实现：快速排序框架，插入排序处理小子文件，随机函数选取split点，双向扫描；
• 第二种实现：最小堆框架，基于fixUp的堆构建策略（数组整体更新，bottom up），通过删除前K个堆顶元素获取最小K个数；
• 第三种实现：最大堆框架，基于fixDown的堆构建策略（0起点插入式，top down），首先构建K个数的最大堆，然后新元素与堆顶元素进行比较，小于则替换现有堆顶元素，更新最大堆；

解题：

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <time.h>

void ShowMinK(int *array, int k) {
        printf("
Min k: 
");
        for(int m=0; m<=k;m++) {
                printf("%d, ",array[m]);
        }
}

void merge(int *array, int i, int split, int j) {
        /**
         * 此版本采用的是双向遍历，left和right指针同时从左右向中间遍历
         * 其他还有单向遍历和三相遍历，此处不作解释
         * */
        /**
         * 首先将split元素交换到j作为参考元素
         * */
        int temp=array[split];
        array[split]=array[j];
        array[j]=temp;

        int left=i; int right=j-1;

        while(true) {
                /**
                 * 两个指针同时相向遍历，当指针相遇（交错）或者满足与array[j]
                 * 的特定关系，则暂时停止。
                 * */
                while(left<right && array[left]<=array[j]) {
                        left++;
                }
                while(right>left && array[right]>array[j]) {
                        right--;
                }

                if(left>=right) break;

                temp=array[left];
                array[left]=array[right];
                array[right]=temp;
                left++;
                right--;
        }
        /**
         * 将split元素从j位置交换回分界位置
         * */
        temp=array[left];
        array[left]=array[j];
        array[j]=temp;
}

void InsertSort(int *array, int i, int j) {
        /**
         * 此版本仅使用最基本的插入排序思想，左边的序列都已经排好序
         * 每一次循环都是讲array[m]插入左边序列
         * 其他版本可以将找到最大值并放到最左边，这样可以省去每次
         * 循环中对左边范围的检查
         * */
        int temp,k;
        for(int m=i+1;m<=j;m++) {
                temp=array[m];
                k=m-1;
                while(k>=i) {
                        if(array[k]>temp) {
                                /**
                                 * 当array[k]大于temp，则将其向前复制
                                 * */
                                array[k+1]=array[k];
                        } else {
                                /**
                                 * 当array[k]小于等于temp，则最终将m插入
                                 * array[k+1],此次插入结束
                                 * */
                                break;
                        }
                        k--;
                }
                /**
                 * 注意不同的跳出条件，是从break跳出的还是k>=i跳出的
                 * */
                array[k+1]=temp;
        }
}

void MinKQuickSort(int *array, int i, int j, int k) {
        /**
         * 当数组长度小于7的时候，直接的插入排序将会优于更小的子递归
         * */

        if(j-i+1 < 7) {
                InsertSort(array, i, j);
                ShowMinK(array, k);
                return;
        }

        /**
         * 使用随机函数rand()选择split的策略，避免最坏情况
         * time()或者getpid()可以作为srand函数的参数
         * */
        if(i>j) return;
        if(i==j && i==k){
                        ShowMinK(array,k);
                        return;
                }
        srand((int)time(0));
        int split=rand()%(j-i+1) + i;
        merge(array, i, split, j);

        if(split > k) {
                /**
                 * 当前的split大于k，所以前k小的数应该在左边部分，k已经是相对i
                 * 的计数，所以需要减去i
                 * */
                MinKQuickSort(array, i, split-1, k);
        } else if(split < k) {
                /**
                 *
                 * 当前的split小于k，所以前k小 的数应该在右边部分，k是相对i的
                 * 计数，现在需要相对split+1，所以需要更改
                 * */
                MinKQuickSort(array, split+1, j, k);
        } else if(split == k) {
                ShowMinK(array, k);
        }
}
/**
 *
 * */
void MinFixUp(int *array, int length, int i) {
        int start=i;
        int temp,father;
        while(start>1 && array[start]<array[start/2]) {

                temp=array[father];
                array[father]=array[start];
                array[start]=temp;
                start/=2;;
        }
}

void MinFixDown(int *array, int length, int i) {
        int s;
        int temp, father;
        while(2*i<=length) {
                s=2*i;
                if(s+1<=length && array[s] > array[s+1]) {
                        s++;
                }
                if(array[i]<=array[s]) break;

                temp=array[i];
                array[i]=array[s];
                array[s]=temp;
                i=s;
        }
}

/**
 * 从最后一个拥有子节点的内部节点开始逆向遍历到根节点
 * */
void BuildMinHeap(int *array, int length) {

        for(int i=length/2;i>=1;i=i-1) {
                MinFixDown(array, length, i);
        }
}

/**
 * 从array[1]开始存储元素，从而简化代码
 * 首先构建最小堆，然后删除堆顶元素，缩小堆大小
 * 更新堆结构，重复K次
 * */
void MinKMiniHeap(int *array, int length, int k) {
        BuildMinHeap(array, length);
        int capability=length;
        for(int i=1;i<=k;i++) {
                printf("%d, ",array[1]);
                array[1]=array[capability];
                capability--;
                MinFixDown(array, capability, 1);
        }
}

void MaxFixUp(int *array, int length, int i) {}

void MaxFixDown(int *array, int length, int i) {}

void BuildMaxHeap(int *array, int k) {}

void MinKMaxHeap(int *array, int length, int k) {
        BuildMaxHeap(array, k);
        for(int i=k+1;i<=length;i++) {
                if(array[1]>array[i]) {
                        array[1]=array[i];
                        MaxFixDown(array, k, 1);
                }
        }

        int capability=k;
        for(int i=1;i<=k;i++) {
                printf("%d, ",array[1]);
                array[1]=array[capability];
                capability--;
                MaxFixDown(array, capability, 1);
        }

}

出题：输入一个整数数组，判断该数组是否给定二元查找树（Binary Search Tree）的部分后序（Post Order）遍历结果（给定二元查找树，判定整数数组是否在其中）；

分析：使用int *position作为对比位置记录

解题：

struct Node {
        int value;
        Node *left;
        Node *right;
};
/**
 * Binary Search Tree可能不是满树，所以有右子树不一定就有左子树
 * 仅当子树中完全找到整个序列才返回true，否则返回false，使用position
 * 记录当前的比较位置
 * */
bool PostOrderCompare(Node *cur, int *array, int length, int *position) {
        bool isLeft=false, isRight=false;
        if(cur->left != NULL) {
                /**
                 * 左子树存在时候的后序遍历
                 * */
                isLeft=PostOrderCompare(cur->left, array, length, position);
                if(!isLeft && cur->right != NULL) {
                        isRight=PostOrderCompare(cur->right, array, length, position);
                }
        } else if(cur->right != NULL) {
                /**
                 * 仅右子树存在时候的后序遍历
                 * */
                isRight=PostOrderCompare(cur->right, array, length, position);
        }

        if(isLeft || isRight) return true;
        /**
         * 左右子树都还没有满足条件，处理当前节点
         * */
        printf("
current node: %d
", cur->value);
        printf("
current position value: %d
", array[*position]);
        if(cur->value == array[*position]) {
                if(*position +1 == length) return true;
                else {
                        /**
                         * 仅当当前值匹配的时候position才更新， 否则直接返回
                         * */
                        *position = *position+1;
                }
        }
        return false;
}