面试练习题

川长思鸟来 2022-08-05 08:23 241阅读 0赞

1,一个数组保存了N个结构，每个结构保存了一个坐标，结构间的坐标都不相同，请问如何找到指定坐标的结构（除了遍历整个数组，是否有更好的办法）？

情况一:如果这些坐标存入数组时候是按照顺序来存的,那就只能遍历整个数组了.
    
    情况二:为了提高查找效率,就需要在插入的时候,考虑将来如何方便查找.
    
    那就可以考虑哈希的方法了. 根据坐标(x,y),通过哈希函数生成一个位置, 
    
    然后把该坐标存在对应的位置上. 这样再将来查找的时候,就能快速找到了, 可能会 一次命中.
    
    这个问题说明: 时间的特点, 就是 前面时间做的事情, 在后面时间发生效果. 
    
    往往这中间是有一个间隔.  但间隔总会过去, 因此, 还是应当适当为 不远的未
    
    来做准备. 如果能够一直 ,为不远的未来准备, 就能够在不远的未来, 为 未来
    
    的未来做准备. 常常这样做,就体会到其中的妙处.

2,现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。（编程珠玑上有此类似的一题，如果有足够的内存的话可以用位图法，即开一个1亿位的bitset，内存为100m/8== 12.5m, 然后如果一个数有出现，对应的bitset上标记为1，最后统计bitset上为0的即可。）

一亿,即是1 0000 0000 ,一个字节char如果是8位, 那就需要 10000 0000/8=1250 0000 字节, 
        1250万字节=1250万Byte = 12500 KB = 12.5MB. 即使电脑也有4G的内存,所以内存足够, 
        那就可以用位图法.
        每个数字占一位, 有就置1, 没有置0, 应该初始化就是全0的, 例如10存在,
    10/8=1 , 10%8=2, 就应该把 第二个字节的,第二个bit位置1.  其他的依次类推. 
    最后统计bit位上为0 的数就可以.
        思考:我为什么要举10这个例子呢? 因为抽象的往往不太好想,尤其是对我这样大脑容量小的人来说, 
        也就比较算是落地了,不然总是在天空飘着,
        不实在. 还有为什么举10呢, 一开始想举例子 1000来着, 可是这样又不太好想了, 
        凡是举例子,还是应该举20以内的数字, 理解起来没有压力.

参考博客  
[http://blog.csdn.net/v\_july\_v/article/details/6855788][http_blog.csdn.net_v_july_v_article_details_6855788]

[http_blog.csdn.net_v_july_v_article_details_6855788]: http://blog.csdn.net/v_july_v/article/details/6855788