查找最小的k个元素(栈和队列)

查找最小的k个元素(栈和队列)

时间: 1ms        内存:1000M

描述:

题目:输入n个整数,输出其中最小的k个。
例如输入123456788个数字,则最小的4个数字为1234

输入:

输入:

8 4

1 2 3 4 5 6 7 8

输出:

1 2 3 4

示例输入:

8 4

1 2 3 4 5 6 7 8

示例输出:

1 2 3 4

提示:

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

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct node{
	int date;
	struct node *link;
}StrNode;
typedef struct{
	StrNode *f;
	StrNode *r;
	int size;
}StrQueue;
void InitQueue(StrQueue *s){
	s->f=malloc(sizeof(StrNode));
	s->f->link=NULL;
	s->r=s->f;
	s->size=MAXSIZE;
}
void Push(StrQueue *s){
	StrNode *p=s->f,*q;
	q=malloc(sizeof(StrNode));
	scanf("%d",&q->date);
	q->link=NULL;
	while(p->link!=NULL){
		if(p->link->date>q->date){
			q->link=p->link;
			p->link=q;
			break;
		}
		else
			p=p->link;
	}
	if(p->link==NULL)
		p->link=q;
}
void Print(StrQueue *s,int m){
	int i=0;
	StrNode *p=s->f;
	while(i++<m){
		printf("%d ",p->link->date);
		p=p->link;
	}
}
int main(){
	int n,k;
	StrQueue s;
	scanf("%d%d",&n,&k);
	InitQueue(&s);
	while(n--){
		Push(&s);
	}
	Print(&s,k);
	return 0;
}

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

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct node{
	int date;
	struct node *link;
}StrNode;
typedef struct{
	StrNode *f;
	StrNode *r;
	int size;
}StrQueue;
void InitQueue(StrQueue *s){
	s->f=malloc(sizeof(StrNode));
	s->f->link=NULL;
	s->r=s->f;
	s->size=MAXSIZE;
}
void Push(StrQueue *s){
	StrNode *p=s->f,*q;
	q=malloc(sizeof(StrNode));
	scanf("%d",&q->date);
	q->link=NULL;
	while(p->link!=NULL){
		if(p->link->date>q->date){
			q->link=p->link;
			p->link=q;
			break;
		}
		else
			p=p->link;
	}
	if(p->link==NULL)
		p->link=q;
}
void Print(StrQueue *s,int m){
	int i=0;
	StrNode *p=s->f;
	while(i++<m){
		printf("%d ",p->link->date);
		p=p->link;
	}
}
int main(){
	int n,k;
	StrQueue s;
	scanf("%d%d",&n,&k);
	InitQueue(&s);
	while(n--){
		Push(&s);
	}
	Print(&s,k);
	return 0;
}

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

点赞

发表评论

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