sxxzhch 发布留言 2008-7-7 20:02 判断6个数互不相等!!(给出源代码谢谢)如题lingluoz 发布留言 2008-7-7 22:02 把六个数放进数组里面。。然后挂两个FOR。一个一个比。。
或者列15个IF。。
思路就是这些。。具体你自己想办法吧。xnm890325 发布留言 2008-7-7 22:04 [tk01] 定义一个数组,用for循环语句和if 条件语句进行判断,就可以了.lingluoz 发布留言 2008-7-7 22:04 把六个数放进数组里面。。然后挂两个FOR。一个一个比。。
或者列15个IF。。
思路就是这些。。具体你自己想办法吧。中学者 发布留言 2008-7-7 22:09 只给汇编码，不过等我考完试 - -cxhiou 发布留言 2008-7-7 23:29 伪码要不？？
态度恶劣StarWing83 发布留言 2008-7-8 01:02 都是O(n^2)的方法啊……有没有线性时间的解决办法？排序再比较邻位可以降到O(nlgn)，有人提供线性方法吗？Rand 发布留言 2008-7-8 01:12 [un]StarWing83[/un] 在 2008-7-8 01:02 的发言：[/bo]
都是O(n^2)的方法啊……有没有线性时间的解决办法？排序再比较邻位可以降到O(nlgn)，有人提供线性方法吗？ [/quote]
我怎么觉得都是O(n！)的方法~StarWing83 发布留言 2008-7-8 01:32 LS：两两比较，不是全排列……StarWing83 发布留言 2008-7-8 01:33 在n^2的方法中，一个简单的优化可以让复杂度降到n(n-1)/2。卧龙孔明 发布留言 2008-7-8 07:35 线性方法容易，写个hashlingluoz 发布留言 2008-7-8 08:09 8知道用hoare算法行不行StarWing83 发布留言 2008-7-8 11:04 [un]卧龙孔明[/un] 在 2008-7-8 07:35 的发言：[/bo]
线性方法容易，写个hash [/quote]
拜托不要老hashhash的……那个叫计数（Count）。
线性的原因是因为计数排序本身就是线性的，这其实还是通过排序进行判断的子方法。
虽然时间的确是线性，但是空间复杂度不理想。
我希望能得到原地判断的线性方法。卧龙孔明 发布留言 2008-7-8 11:05 只有6个数,hash冲突的几率很小，并且，假设真有冲突，也只是最多5个冲突。
如果数据规模小，用个countsort也可以StarWing83 发布留言 2008-7-8 11:22 哦？真的是Hash？？
我还不是很了解，能具体说明一下么？谢谢~~
主要是，hash以后，如何判断是否相等。卧龙孔明 发布留言 2008-7-8 11:27 [un]StarWing83[/un] 在 2008-7-8 11:22 的发言：[/bo]
哦？真的是Hash？？
我还不是很了解，能具体说明一下么？谢谢~~
主要是，hash以后，如何判断是否相等。 [/quote]
设标志为Flag,初始=1
假如读入的元素（设为X)放入hash后发现冲突，那么与hash中的数比较，如果不相等，那么解决hash冲突问题（这里，开闭散列就不说了，学长应该明白），否则将flag=0，并退出
最后，if(flag) 不等 else 有相等的卧龙孔明 发布留言 2008-7-8 11:31 给个简单的程序(C)
char hash[1000000]={0};
char flag=1;
int i,temp;
for(i=0;i<6;++i)
{
scanf("%d",&temp);
if(hash[temp%999991])
{
flag=0; break;
} else hash[temp%999991]=1;
}
if(flag) printf("互不相等");StarWing83 发布留言 2008-7-8 11:37 明白了……通过hash缩小比较范围……的确可以达到n的复杂度，谢谢孔明兄~~~
那有没有原地判定的线性方法呢？卧龙孔明 发布留言 2008-7-8 11:43 [quote][un]StarWing83[/un] 在 2008-7-8 11:37 的发言：[/bo]
明白了……通过hash缩小比较范围……的确可以达到n的复杂度，谢谢孔明兄~~~
那有没有原地判定的线性方法呢？ [/quote]
不清楚，不过这个题部分类似于NOIP2007提高组第一个，由那题的解题思路看，如果还要知道互不相等的个数，可以用随机化二叉排序树并改进一下，接点中count记录count所在节点的数据出现的个数，这样，设一共不重复的数据（例如1 2 2 3算3个数据）为n，那么复杂度为nlogn，即，如果重复数据较多，那么此方法的速率高于qsort很多卧龙孔明 发布留言 2008-7-8 11:46 对于这个题，想必数据中重复的很少或者没有，所以用我说的那个方法，还没有quicksort快
[1] [2] 下一页
特别说明：如网页特效代码中有引用图片文件等，请自己下载到本地调试！ |
|
[] [返回] [打 印] [收 藏] [评 论] |
|
|
|
|
|
|
