剑指offer第六天

面试题21 包含min函数的栈

实现一个能够得到栈的最小元素的min函数，在该栈中调用min，push，pop的时间复杂度都是O(1)
思路 把每次的最小元素保存起来放到另一个辅助栈里
代码

#pragma mark-包含min函数的栈
void push(struct stack *data,struct stack *min,int x){
data->top++;
data->data[data->top]=x;
//如果辅助栈为空或者新加入的值小于最小值
if (min->top==-1 || x<min->data[min->top]) {
    min->top++;
    min->data[min->top]=x;
}else{
    int t=min->data[min->top];
    min->top++;
    min->data[min->top]=t;
}
}
void pop(struct stack *data,struct stack *min){
data->top--;
min->top--;
}
int min(struct stack *min){
if (min->top==-1) {
    return 0;
}else{
    return min->data[min->top];
}
}
void minstack(){
struct stack s1,s2;
s1.top=-1;
s2.top=-1;
push(&s1, &s2, 3);
push(&s1, &s2, 4);
push(&s1, &s2, 2);
push(&s1, &s2, 5);
printf("%d", min(&s2));
}

面试题23 二叉树的层次遍历

思路 每一次打印一个节点的时候，如果该节点有子节点，则把该节点的子节点放到一个队列的末尾。该节点出队，直至队列为空。
代码

#pragma mark-层次遍历二叉树
void Toptobottom(struct BinaryTreeNode     *root,struct queue *q){
if (!root) {
    return;
}
//把根节点加入队列
q->tail++;
q->data[q->tail]=root;
//当队列不空时
while (q->tail-q->head!=0) {
    //取出队列头节点
    struct BinaryTreeNode *node=q->data[q->head];
    printf("%d",node->value);
    q->head++;
    //将左右孩子加入队列
    if (node->leftchild) {
        q->tail++;
        q->data[q->tail]=node->leftchild;
    }
    if (node->rightchild) {
        q->tail++;
        q->data[q->tail]=node->rightchild;
    }

}
}

面试题29 数组中出现次数超过一半的数字

思路 数组中一个数字出现次数超过一半，说明其他元素出现次数总和没有它多。我们保存两个值，一个是数组中的数字，一个是次数，该数字出现一次次数加一，出现别的数字就减一，如果次数为0，保存新的数字，到最后保存的数字就是数组中出现次数超过一半的数字。
代码

 #pragma mark-数组中出现次数超过一半的元素
 //思路 一个数出现次数超过一半 那么它出现次数比其他所有数总和还要多 那么每出现一次加1 出现别的数减1 最后该数肯定大于0
int MorethanHalf(int a[],int length){
int temp=a[0];
int count=1;
for (int i=1; i<length; i++) {
    if (count==0) {
        temp=a[i];
        count++;
    }else if (a[i]==temp){
        count++;
    }else{
        count--;
    }
        }
return temp;
}
void checkMorethanHalf(){
int a[5]={2,2,3,4,2};
printf("%d",MorethanHalf(a, 5));
}

面试题30 输入n个整数，找出其中最小的k个数

思路一 利用快排的思想
代码

//利用快排的思想 快速排序一趟过后 比基准元素小的元素全在左边 只要左边的数目等于k 即符合题意
void kmin(int left,int right,int a[],int k){
int i,j,t,temp;
if (left>right) {
    return;
}
temp=a[left];
i=left;
j=right;
while (i!=j) {
    while (a[j]>=temp && i<j) {
        j--;
    }
    while (a[i]<=temp && i<j) {
        i++;
    }
    if (i<j) {
        t=a[j];
        a[j]=a[i];
        a[i]=t;
    }
}
a[left]=a[i];
a[i]=temp;
//如果i等于k 则i左边正好有k个数
if (i==k) {
    for (int i=0; i<k; i++) {
        printf("%d",a[i]);
    }
    //如果i大于k 则对i左边继续排
}else if (i>k){
    kmin(left, i-1, a, k);
    //如果i小于k 则对i右边继续排
}else{
    kmin(i+1, right, a, k);
}
}

另一种思路 如果n很大，是海量数据怎么办
创建一个大小为k的容器，每次读进一个数字。
若容器不满，数字加入容器。
若容器满，找出容器中的最大值和数字进行比较，若数字较小，则替换。由于我们需要经常进行替换和查找最大值的工作，所以容器可以选择为红黑树。