查找【数组】

查找【数组】

时间: 1ms        内存:128M

描述:

利用search(a,n,k)函数在数组a的前n(n>=1)个元素中找出前k个(1<=k<=n)小的值。假设数组a中各元素的值都不相同。

输入:

数组中各元素

n k

输出:

a中前k个小的值

示例输入:

5 6 2 1 4 85 78 11
7 4

示例输出:

5 2 1 4

提示:

参考答案(内存最优[756]):

#include<stdio.h>
#include<string.h>
int b[1000];
void sorta(int a[],int n)
{
	int i,j,t,k;
	for(i=0;i<n;i++)
	{
		k=i;
		for(j=i+1;j<n;j++)
		{
			if(a[k]>a[j])
				k=j;
		}
		t=a[k];
		a[k]=a[i];
		a[i]=t;
		t=b[k];
		b[k]=b[i];
		b[i]=t;
	}
}
void sortb(int a[],int k)
{
	int i,j,t,k0;
	for(i=0;i<k;i++)
	{
		k0=i;
		for(j=i+1;j<k;j++)
		{
			if(b[k0]>b[j])
				k0=j;
		}
		t=a[k0];
		a[k0]=a[i];
		a[i]=t;
		t=b[k0];
		b[k0]=b[i];
		b[i]=t;
	}
}
void search(int a[],int n,int k)
{
	int i,x;
	sorta(a,n);
	sortb(a,k);
	for(i=0;i<k;i++)
	{
		printf("%d",a[i]);
		if(i!=k-1)
			printf(" ");
	}
	printf("\n");
}
int main()
{
	int a[1000];
	int n,k,i;
	char c;
	for(i=0;;i++)
	{
		scanf("%d%c",&a[i],&c);
		b[i]=i;
		if(c!=' ')
			break;
	}
	scanf("%d%d",&n,&k);
	search(a,n,k);
	return 0;
}

参考答案(时间最优[0]):

#include<stdio.h>
#include<string.h>
int b[1000];
void sorta(int a[],int n)
{
	int i,j,t,k;
	for(i=0;i<n;i++)
	{
		k=i;
		for(j=i+1;j<n;j++)
		{
			if(a[k]>a[j])
				k=j;
		}
		t=a[k];
		a[k]=a[i];
		a[i]=t;
		t=b[k];
		b[k]=b[i];
		b[i]=t;
	}
}
void sortb(int a[],int k)
{
	int i,j,t,k0;
	for(i=0;i<k;i++)
	{
		k0=i;
		for(j=i+1;j<k;j++)
		{
			if(b[k0]>b[j])
				k0=j;
		}
		t=a[k0];
		a[k0]=a[i];
		a[i]=t;
		t=b[k0];
		b[k0]=b[i];
		b[i]=t;
	}
}
void search(int a[],int n,int k)
{
	int i,x;
	sorta(a,n);
	sortb(a,k);
	for(i=0;i<k;i++)
	{
		printf("%d",a[i]);
		if(i!=k-1)
			printf(" ");
	}
	printf("\n");
}
int main()
{
	int a[1000];
	int n,k,i;
	char c;
	for(i=0;;i++)
	{
		scanf("%d%c",&a[i],&c);
		b[i]=i;
		if(c!=' ')
			break;
	}
	scanf("%d%d",&n,&k);
	search(a,n,k);
	return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注