| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4071 人关注过本帖
标题:【时间复杂度小的解法】数1-100中的奇数无序排列,缺一个数,怎么快速找出来 ...
取消只看楼主 加入收藏
超超超1
Rank: 1
等 级:新手上路
帖 子:22
专家分:1
注 册:2013-5-21
结帖率:80%
收藏
已结贴  问题点数:20 回复次数:2 
【时间复杂度小的解法】数1-100中的奇数无序排列,缺一个数,怎么快速找出来?
问:c 里面的搜索算法有几种
答:没听懂
问:有1-100的所有奇数,无序排列,怎么找出缺的那个
答:先把所有 1-100 的奇数加起来减去他的和
问:时间复杂度太大 有简单的吗?


这是计算机研究生复试时候的问题。
搜索算法,这个该怎么答?
我在想这个找出缺的数,方法有:①求和相减;②排序,判断;③比较,判断;④c语言的位运算中的异或运算(“半加运算”);⑤集合观点,补集全集。

关于④:把这些无序的数和1到100中的所有奇数作“半加运算”,然后就得到这个缺的数。这个只是用加法,没有进位,没有逻辑判断,算简单了吗?

关于⑤:从数学的角度来说,把1到100中的奇数设为全集,把这些无序的数设为其中的一个子集,它的补集就是所缺的数。想法是简单的,弱弱问下c语言中的函数库什么的,有提供集合表达方式的吗?其他编程语言呢?能满足老师的要求吗?

除了上面说的几个方法 ,还有方法吗?



[ 本帖最后由 超超超1 于 2013-8-15 16:11 编辑 ]
搜索更多相关主题的帖子: 研究生复试 计算机 c语言 
2013-08-15 16:07
超超超1
Rank: 1
等 级:新手上路
帖 子:22
专家分:1
注 册:2013-5-21
收藏
得分:0 
以下是引用liu122430950在2013-8-15 20:11:05的发言:

搜索算法指的是查找算法吗?
那主要就有hash表,B-树,平衡BST树,BST树,折半,顺序,查找表

只要求时间复杂度最小?还有这个无序排列长短不知道,个人认为不能用上述方法
那我就用空间换时间吧,思想是
设奇数个数为N
用一数组记录0-99的全部奇数,可用a[2][N];第二维记录各个奇数的次数起到计数作用,初始化0;
在用一temp[100]记录各数的出现次数起到计数作用,初始化0;
之后
设b[M]存储了该无序奇数序列,M表示长度
void resualt(int &b[],int M)
{
    int temp[100]={0};
    int i=0;
    for(;i!=(M-1);i++)
    {
       ( temp])++;
    }
    mid_resualt(temp);
    for(i=0;i!=N;i++)
    {
        if(a[1]==0)
            printf("%d 未出现\r\n",a[0]);      
    }
}
//遍历数组a[1][M];
void mid_resualt(int &temp[])
{
    int i=0;
    for(;i!=N;i++)
        {
        a[1]=temp[a[0]];//a[0][N]存储0-99所有的奇数,temp[k]表示某奇数k出现的次数,a[1]表示在奇数集合中k出现的次数;
        }
}
思想就是这些了,一些细节方面的问题,楼主自己思考下吧,毕竟我只想给你思路而已
表示没怎么看懂,好深奥啊!
2013-08-17 17:30
超超超1
Rank: 1
等 级:新手上路
帖 子:22
专家分:1
注 册:2013-5-21
收藏
得分:0 
回复 7楼 liu122430950
lz只是菜鸟,我再学点会回来仔细看的
2013-08-18 09:14
快速回复:【时间复杂度小的解法】数1-100中的奇数无序排列,缺一个数,怎么快速 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016446 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved