问：c 里面的搜索算法有几种
答：没听懂
问：有1-100的所有奇数，无序排列，怎么找出缺的那个
答：先把所有 1-100 的奇数加起来减去他的和
问：时间复杂度太大 有简单的吗？


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

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

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

除了上面说的几个方法 ，还有方法吗？



[ 本帖最后由 超超超1 于 2013-8-15 16:11 编辑 ]

“答：先把所有 1-100 的奇数加起来减去他的和 ”
------ 这个答案是很好的呀，(1+99)*50/2 - sum，时间复杂度在求sum上，为O(n)

“问：时间复杂度太大 有简单的吗？”
------ 从理论上，最低的时间复杂度就是O(n)，不可能有更简单的

问：c 里面的搜索算法有几种
答：没听懂
------ 答得很好，这样的面试官，我觉得你还是换个学校读研吧^_^

弱弱问下c语言中的函数库什么的，有提供集合表达方式的吗？其他编程语言呢？
------ 没有；C++ 中有 std::set_ 开头的集合运算函数

小而言之不就深搜和广搜吗，这个问题很极端？

搜索算法指的是查找算法吗？
那主要就有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[b[i]])++;
    }
    mid_resualt(temp);
    for(i=0;i!=N;i++)
    {
        if(a[1][i]==0)
            printf("%d 未出现\r\n",a[0][i]);      
    }
}
//遍历数组a[1][M]；
void mid_resualt(int &temp[])
{
    int i=0;
    for(;i!=N;i++)
        {
        a[1][i]=temp[a[0][i]];//a[0][N]存储0-99所有的奇数，temp[k]表示某奇数k出现的次数，a[1][i]表示在奇数集合中k出现的次数；
        }
}
思想就是这些了，一些细节方面的问题，楼主自己思考下吧，毕竟我只想给你思路而已。

表示没怎么看懂，好深奥啊！

,让我情何以堪。。。。。。。。

lz只是菜鸟，我再学点会回来仔细看的