首页 > 代码库 > 最小的k个数
最小的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 44 5 1 6 2 7 3 8
- 例子输出:
-
1 2 3 4
思路1:使用高速排序(或者其它排序)对这n个数进行排序。取出前k个就可以(O(nlogn))。思路2:我们能够使用快排的partition操作来解决这个问题。假设基于数组的第k个数字进行调整。使得比第k个数字小的全部数字出如今其左边。而比该数字大的出如今右边,这样,位于数组中左边的k个数字即为所求。(O(n))
方案2代码: -
/* 最小的k个数 by Rowandjj 2014/8/9 */ #include<stdio.h> #include<stdlib.h> int partition(int arr[],int low,int high) { int val = arr[low]; while(low < high) { while(low < high && arr[high] >= val) { high--; } arr[low] = arr[high]; while(low < high && arr[low] <= val) { low++; } arr[high] = arr[low]; } arr[low] = val; return low; } //获取最小的k个数 void GetLeastNumbers(int input[],int n,int output[],int k) { if(input == NULL || output == NULL || n<=0 || k<=0 || k > n) { return; } int low = 0,high = n-1; int index = partition(input,low,high); while(index != k-1) { if(index > k-1) { high = index - 1; index = partition(input,low,high); }else { low = index+1; index = partition(input,low,high); } } for(int i = 0; i < k; i++) { output[i] = input[i]; } } //------------------------- //这题要求最小的k个数保持有序,故而使用快排对其进行排序 void QuickSort(int arr[],int low,int high) { if(arr == NULL || low >= high) { return; } int index = partition(arr,low,high); QuickSort(arr,low,index-1); QuickSort(arr,index+1,high); } int main() { int n,k; int output[200000]; while(scanf("%d %d",&n,&k) != EOF) { if(n <= 0 || k <= 0 || k > n) { continue; } int *arr = (int*)malloc(sizeof(int)*n); if(!arr) { exit(-1); } for(int i = 0; i < n; i++) { scanf("%d",arr+i); } GetLeastNumbers(arr,n,output,k); QuickSort(output,0,k-1); for(int j = 0; j < k; j++) { if(j == k-1) { printf("%d\n",output[j]); }else { printf("%d ",output[j]); } } free(arr); } return 0; }
[适合处理海量数据]思路3:能够先创建一个大小为k的数据容器来存储最小的k个数字,接下来我们每次从输入的n个整数中读入一个数,假设容器中已有的数字少于k个,则直接把这次读入的整数放到容器中,假设容器中已有k个数字,此时我们不再插入新的数字。而仅仅能替换已有的数字。找出这已有的k个数中的最大值,然后拿这次待插入的整数和最大值进行比較,假设待插入的值比当前已有的最大值小,则用这个数替换当前已有的最大值,假设待插入的值比当前已有的最大值还要大,那么抛弃这个数。
容器能够使用大顶堆来实现。大顶堆的根始终最大。我们仅仅需将待插入的整数和堆顶进行比較就可以,假设发生替换,则仅仅需调整大顶堆堆顶元素(能够使用堆排序中用到的那个HeapAdjust函数)。
代码:/* 最小的k个数 by Rowandjj 2014/8/10 */ #include<stdio.h> #include<stdlib.h> void HeapAdjust(int arr[],int start,int end) { if(arr == NULL || start < 0 || end <= 0 || start >= end) { return; } int temp = arr[start]; int i = start*2+1; while(i <= end) { if(i+1<=end && arr[i+1]>arr[i]) { i++; } if(temp > arr[i]) { break; } arr[start] = arr[i]; start = i; i = i*2+1; } arr[start] = temp; } bool GetLeastNumbers(int input[],int n,int output[],int k) { if(input == NULL || output == NULL || n <= 0 || k <= 0 || k > n) { return false; } int count = 0; bool needBuildHeap = true; for(int i = 0; i < n; i++) { if(count < k) { output[count++] = input[i]; }else { //第一次须要总体建堆 if(needBuildHeap) { for(int j = k/2-1;j >= 0; j--)//建堆,从第一个非叶子结点開始 { HeapAdjust(output,j,k-1); } needBuildHeap = false; } //大顶堆建好之后,比較当前遍历的整数与堆顶元素大小 if(input[i] >= output[0])//大于等于堆顶元素 { continue;//舍弃 } //假设比堆顶元素小,那么须要交换 output[0] = input[i]; HeapAdjust(output,0,k-1);//又一次调整为大顶堆 } } return true; } //------------------------------------------ //由于要求从小到大排序,故而这里来一个堆排序 void HeapSort(int arr[],int len) { if(arr == NULL || len <= 1) { return; } int i; for(i = len/2-1; i >= 0; i--) { HeapAdjust(arr,i,len-1); } for(i = len-1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; HeapAdjust(arr,0,i-1); } } int main() { int n,k; while(scanf("%d %d",&n,&k) != EOF) { if(n <= 0 || k <= 0) { continue; } int output[200000]; int *arr = (int*)malloc(sizeof(int)*n); if(!arr) { exit(-1); } int i; for(i = 0; i < n; i++) { scanf("%d",arr+i); } GetLeastNumbers(arr,n,output,k); HeapSort(output,k); for(i = 0; i < k; i++) { if(i == k-1) { printf("%d\n",output[i]); }else { printf("%d ",output[i]); } } free(arr); } return 0; }
最小的k个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。