请教一个问题更优的算法

C语言 码拜 6年前 (2015-05-11) 520次浏览 0个评论
 

这是题目的内容:
请教一个问题更优的算法
请教一个问题更优的算法

我个人是这样想的:
先将要输入的所有坐标存到一个结构数组(结构含有序号,横坐标,纵坐标)中,然后再遍历所有结构数组,对每个结构按x,y的情况用选择排序法进行排序,最后再遍历所有结构数组依次输出其中的序号。但觉得这样做既耗时间有耗内存,请问各位大神能没有更好的思路或解法,麻烦指点一下,谢谢

10分
使用qsort():

#include <search.h>
typedef struct point
{
	int s;
	int x;
	int y;
}Point;
Point *ps;
int i, n;
int cmp(Point *p1, Point *p2)
{
	if (p1->x < p2->x) return 0;
	else if (p1->x > p2->x) return 1;
	else return p1->y > p2->y;
}
int main()
{
	scanf("%d", &n);
	ps = malloc(sizeof(Point)*n);
	i = 0;
	//读入坐标
	while (i < n)
	{
		scanf("%d%d%d", &ps[i].s, &ps[i].x, &ps[i].y);
		i++;
	}
	qsort(ps, n, sizeof(Point), cmp);
	for (i = 0; i < n; i++) printf("%d ", ps[i].s);
	printf("\n");
	free(ps);
	return 0;
}
5分
我的思路是用内存换时间
其实X坐标的个数最多也就20W,那就弄个大小是20W的数组,每个数组的索引是X,每个数组的元素是一个链表,链表按照Y来排序
当然,这种算法如果遇到所有X相同,只有Y不同的时候,那效率就灰常低了

空间时间折中的排序算法是桶排序,原理类似,但是内存用的少一些,楼主可以搜索一下,看看会不会有启发

5分
感觉这个数据是<10W的 用快排可能好点把?
引用 2 楼 hnwyllmm 的回复:

我的思路是用内存换时间
其实X坐标的个数最多也就20W,那就弄个大小是20W的数组,每个数组的索引是X,每个数组的元素是一个链表,链表按照Y来排序
当然,这种算法如果遇到所有X相同,只有Y不同的时候,那效率就灰常低了

空间时间折中的排序算法是桶排序,原理类似,但是内存用的少一些,楼主可以搜索一下,看看会不会有启发

好的,我试试

引用 2 楼 hnwyllmm 的回复:

我的思路是用内存换时间
其实X坐标的个数最多也就20W,那就弄个大小是20W的数组,每个数组的索引是X,每个数组的元素是一个链表,链表按照Y来排序
当然,这种算法如果遇到所有X相同,只有Y不同的时候,那效率就灰常低了

空间时间折中的排序算法是桶排序,原理类似,但是内存用的少一些,楼主可以搜索一下,看看会不会有启发

引用 2 楼 hnwyllmm 的回复:

我的思路是用内存换时间
其实X坐标的个数最多也就20W,那就弄个大小是20W的数组,每个数组的索引是X,每个数组的元素是一个链表,链表按照Y来排序
当然,这种算法如果遇到所有X相同,只有Y不同的时候,那效率就灰常低了

空间时间折中的排序算法是桶排序,原理类似,但是内存用的少一些,楼主可以搜索一下,看看会不会有启发

你好,这是我自己写的代码,但提交后是Time Limit Exceeded ,麻烦指点一下其中可以优化的地方,谢谢

#include<stdio.h>
#include<stdlib.h>
struct zuobiao
{
    int xuhao;
    int x;
    int y;
};

int main()
{
    int n,i,t;

    struct zuobiao *p;

    scanf(“%d”,&n);

    p=(struct zuobiao*)malloc((n+1)*sizeof(struct zuobiao));

    for(i=1;i<=n;i++)
    {
        scanf(“%d%d%d”,&(p+i)->xuhao,&(p+i)->x,&(p+i)->y);
    }

    for(i=1;i<n;i++)
        for(t=i+1;t<=n;t++)
    {
        if(((p+i)->x)>((p+t)->x)||((p+i)->x)==((p+t)->x)&&((p+i)->y)>((p+t)->y))
        {
            p[0]=p[i];
            p[i]=p[t];
            p[t]=p[0];
        }
    }

    for(i=1;i<=n;i++)
        printf(“%d “,(p+i)->xuhao);

    printf(“\n”);
    
    return 0;
}

5分
关于排序,还是数据结构里面的几种算法比较成熟,这里可以使用哈希排序算法,n lg(n),的时间复杂度,用两个嵌套就行了
5分
楼主你用的是冒泡排序吧,这个有什么说的,肯定超时,最慢的算法
5分
<1000个元素,冒泡排序
<100000个元素,qsort函数
<10000000个元素,放数据库中,建索引,(B+树排序)
≥10000000个元素,没用到过。
5分
两种方案:

1:先输入所有数据,然后用快排排序,快排平均时间复杂度是O(nlogn),但最坏情况时间复杂度为O(n^2),不过快排函数C语言的标准库已经帮你实现了:qsort,直接用就可以了。

2:用红黑树保存数据,在输入数据的时候就直接进行了排序,红黑树插入操作最坏情况时间复杂度为O(log(n)),所以输入+排序总的时间复杂度为O(nlogn),但红黑树你要自己实现。

引用 1 楼 zhangxiangDavaid 的回复:

使用qsort():

#include <search.h>
typedef struct point
{
	int s;
	int x;
	int y;
}Point;
Point *ps;
int i, n;
int cmp(Point *p1, Point *p2)
{
	if (p1->x < p2->x) return 0;
	else if (p1->x > p2->x) return 1;
	else return p1->y > p2->y;
}
int main()
{
	scanf("%d", &n);
	ps = malloc(sizeof(Point)*n);
	i = 0;
	//读入坐标
	while (i < n)
	{
		scanf("%d%d%d", &ps[i].s, &ps[i].x, &ps[i].y);
		i++;
	}
	qsort(ps, n, sizeof(Point), cmp);
	for (i = 0; i < n; i++) printf("%d ", ps[i].s);
	printf("\n");
	free(ps);
	return 0;
}
引用 1 楼 zhangxiangDavaid 的回复:

使用qsort():

#include <search.h>
typedef struct point
{
	int s;
	int x;
	int y;
}Point;
Point *ps;
int i, n;
int cmp(Point *p1, Point *p2)
{
	if (p1->x < p2->x) return 0;
	else if (p1->x > p2->x) return 1;
	else return p1->y > p2->y;
}
int main()
{
	scanf("%d", &n);
	ps = malloc(sizeof(Point)*n);
	i = 0;
	//读入坐标
	while (i < n)
	{
		scanf("%d%d%d", &ps[i].s, &ps[i].x, &ps[i].y);
		i++;
	}
	qsort(ps, n, sizeof(Point), cmp);
	for (i = 0; i < n; i++) printf("%d ", ps[i].s);
	printf("\n");
	free(ps);
	return 0;
}

谢谢指点

谢谢各位的指点,学到了不少新知识

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明请教一个问题更优的算法
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!