首页 > ACM题库 > 九度OJ > 九度-1371-最小的K个数
2014
04-16

九度-1371-最小的K个数

这个题目再经典不过了,也是常见的面试题。

题目描述:
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
输入:
每个测试案例包括2行:第一行为2个整数n,k(1<=n,k<=200000),表示数组的长度。

第二行包含n个整数,表示这n个数,数组中的数的范围是[0,1000 000 000]。

输出:
对应每个测试案例,输出最小的k个数,并按从小到大顺序打印。
样例输入:
8 4
4 5 1 6 2 7 3 8
样例输出:
1 2 3 4

此题的不同之处是最后的输出结果需要是排序过的,一般是不要求这个的。

最常见的解法就是使用快速排序和大顶堆。

方法一使用快速排序的思想,划分的操作不用改,对递归部分稍作修改

#include<stdio.h>
#include<algorithm>
using namespace std;
int partition(int arr[], int s, int e){
    int x = arr[s];
    int r = e+1;
    int l = s;
    while(l < r){
        while(l<e && arr[++l] <= x);
        while(r>s && arr[--r] > x);
        if(l >= r) break;
        swap(arr[r],  arr[l]);
    }
    arr[s] = arr[r];
    arr[r] = x;
    return r;
}
int k;
void minK(int arr[],int start,int end){
    if(start >= end) return;
    int index = partition(arr,start,end);
    if(index == k) return;
    //类似二分的思想,比快速排序要少一个递归
    if(index > k) minK(arr,start,index-1);
    else minK(arr,index+1,end);
}
const int M = 200001;
int n,arr[M];
int main()
{
    while(scanf("%d%d",&n, &k) != EOF){
        for(int i=0; i<n; i++){
            scanf("%d", &arr[i]);
        }
         --k;
         minK(arr,0,n-1);
         sort(arr,arr+k+1);//输出结果需要是排序的
         for(int i=0; i<k; i++)
             printf("%d ",arr[i]);
         printf("%d\n",arr[k]);
    }
    return 0;
}

/**************************************************************
    Problem: 1371
    User: coder
    Language: C++
    Result: Accepted
    Time:810 ms
    Memory:1800 kb
****************************************************************/

方法二使用 大顶堆。

#include <algorithm>
#include <cstdio>
using namespace std;
int n,k,a[200000];
void adjustHeap(int idx){
    int l = idx*2 + 1;
    int r = idx*2 + 2;
    int largeIndex = idx;
    //先检查边界。k即为要创建的堆的大小
    while( l<k  || r<k ){
        if(l<k && a[l] > a[largeIndex]) largeIndex = l;
        if(r<k && a[r] > a[largeIndex]) largeIndex = r;
        if(largeIndex != idx){
            //交换 root和子节点。
            swap(a[idx], a[largeIndex]);
            //交换之后继续调整子节点
            idx = largeIndex;
            l = idx*2 + 1;
            r = idx*2 + 2;
        }else{
            break; //无需调整
        }
    }
}
void buildHeap(){
    for(int i= (k-1)/2; i>=0; i--){
        adjustHeap(i);
    }
}
int main(){
    while(scanf("%d%d", &n, &k) != EOF){
        for(int i = 0; i < k; i++)
            scanf("%d", &a[i]);
        buildHeap();
        for(int i = k; i < n; i++){
            scanf("%d", &a[i]);
            if(a[0] > a[i]){
                swap(a[0],a[i]);
                adjustHeap(0);
            }
        }
        sort(a,a+k);
        for(int i = 0; i<k-1; i++)
                printf("%d ", a[i]);
        printf("%d\n", a[k-1]);
    }
}

/**************************************************************
    Problem: 1371
    User: coder
    Language: C++
    Result: Accepted
    Time:910 ms
    Memory:1800 kb
****************************************************************/

可见效率其实相差并不大。


  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. 不考虑最后将结果排序的话,快排的时间复杂度是O(N) ,而堆排的是O(N*logK),这样比较看,快排快