• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C++查找数组中最小的若干个元素

OC/C/C++ 水墨上仙 2436次浏览

题目:
输入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;
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C++查找数组中最小的若干个元素
喜欢 (1)
加载中……