题目:
输入n个整数,输出其中的k个最小数。
例如:
例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。
解题思路:
当然,方法最简单的就是对这n个整数都进行排序操作,但这种方法的时间复杂度尤其的高。
因此,我采用了,用另外k个空间,以换取时间的方法 。每次从输入的n个整数中读入一个数。如果数组中已经插入的元素少于k个,则将读入的整数直接放到数组中。否则就是长度为k的数组已经满了,不能再往数组里插入元素,只能进行替换了。
如果读入的这个整数比数组中已有k个整数的最大值要小,则用读入的这个整数替换这个最大值;如果读入的整数比数组中已有k个整数的最大值还要大,则读入的这个整数不可能是最小的k个整数之一,抛弃这个整数。这种思路相当于只要排序k个整数,因此时间复杂可以降到O(n+nlogk)。通常情况下k要远小于n,所以这种办法要优于前面的思路。
#include<limits.h> using namespace std; #define N 100 #define K 5 void bubble_sort_k(int array[],int num) { int i = 0; int j = 0; //int flag = 0; int temp = 0; for(i = 0;i < num; i++) { //flag = 1; for(j = i+1; j < num; j++) { if(array[i] > array[j]) { temp = array[j]; array[j] = array[i]; array[i] = temp; //flag = 0; } } //if(flag == 1) // break; } return; } int main() { int array_n[N] = {INT_MAX}; //int array_n[N] = {9,8,7,6,5,4,3,2,1}; int array_k[K] = {INT_MAX}; int i = 0; int j = 0; int m = 0; int number = 0; while(cin>>i) { array_n[number] = i; number++; } //number = 9; for(j=0;j<K;j++) { array_k[j] = array_n[j]; } bubble_sort_k(array_k,K); for(i = K;i<number;i++) { for(j = 0;j<K;j++)//从数组最小的元素开始比较 { if(array_n[i] < array_k[j]) { for(int n = K-1;n > j;n--)//找到该数比哪个元素小之后,将其后的部分后移,即将最大元素移出数组。 { array_k[n] = array_k[n-1]; } array_k[j] = array_n[i]; break; } } } for(m=0;m<K;m++) { cout<<array_k[m]<<endl; } return 0; }