这是我面试A公司时碰到的算法题,题目大意是一本书缺了一页,然后书页顺序被打乱,问如何迅速找到缺失的那一页?
思路:其实就是在乱序数组里面找缺失的一个数,有以下方法
1、直接排序,然后遍历一次 时间复杂度O(NlogN),不需要额外空间
2、用bitmap思想,开一个大数组,可以用bitset以节省空间,遍历一遍该数组,出现的数字置位为1,遍历完毕后,没有置位的那一位对应的数就是缺失的数字,时间复杂度O(N),但是需要O(N)的额外空间
3、原地桶排序思想,遍历数组,如果脚标与值相等不做任何处理;否则交换该数到其值索引的那个位置,对于被占用位置的数字,采用同样的方法放到其值索引的位置,直到数组末尾,此时只有空缺的那个数为脚标的那个数的值不等于其脚标。复杂度O(N),且没有额外空间,是最佳算法
关于该算法的复杂度分析存在疑问,有一种观点认为是O(N)-O(N^2)之间,见http://topic.csdn.net/u/20120317/16/879e94ef-a873-4de3-ba9a-5efb47f5e51b.html?seed=138344854&r=77943877#r_77943877
4、巧妙的数学方法,这是我和一个同学讨论得到的,由于知道书本的总页数,于是利用求和公式直接可以计算出不缺页的情况下的页码之和sum,缺的页码就是sum减去实际所有页码之和,妙哉。利用数组特殊性,可以避免排序的考虑,真是独辟蹊径。
算法3实现如下,以10个数字为例
程序可以在O(N)时间内找到缺失的数字5,且不占用额外空间。
分享到:
相关推荐
最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列...
上海Linux运维工程师-面试题-个人总结).docx上海Linux运维工程师-面试题-个人总结).docx上海Linux运维工程师-面试题-个人总结).docx上海Linux运维工程师-面试题-个人总结).docx上海Linux运维工程师-面试题-个人总结)...
java面试题-50java面试题-50道最容易考的java题java面试题-50道最容易考的java题java面试题-50道最容易考的java题java面试题-50道最容易考的java题java面试题-50道最容易考的java题java面试题-50道最容易考的java题...
上海Linux运维工程师-面试题-个人总结).pdf上海Linux运维工程师-面试题-个人总结).pdf上海Linux运维工程师-面试题-个人总结).pdf上海Linux运维工程师-面试题-个人总结).pdf上海Linux运维工程师-面试题-个人总结).pdf...
最新各大公司企业真实面试题-Java面试题最新各大公司企业真实面试题-Java面试题
算法大全-面试题-链表-栈-二叉树-数据结构
java面试题-外企软件工程师面试题大全.rarjava面试题-外企软件工程师面试题大全.rarjava面试题-外企软件工程师面试题大全.rarjava面试题-外企软件工程师面试题大全.rar
史上最全的机器学习面试题-机器学习爱好者必看.docx史上最全的机器学习面试题-机器学习爱好者必看.docx史上最全的机器学习面试题-机器学习爱好者必看.docx史上最全的机器学习面试题-机器学习爱好者必看.docx史上最全...
史上最全的机器学习面试题-机器学习爱好者必看.pdf史上最全的机器学习面试题-机器学习爱好者必看.pdf史上最全的机器学习面试题-机器学习爱好者必看.pdf史上最全的机器学习面试题-机器学习爱好者必看.pdf史上最全的...
前端面试题-企业面试真题.zip前端面试题-企业面试真题.zip前端面试题-企业面试真题.zip前端面试题-企业面试真题.zip前端面试题-企业面试真题.zip前端面试题-企业面试真题.zip
史上最全的机器学习面试题-机器学习爱好者必看 (2).pdf史上最全的机器学习面试题-机器学习爱好者必看 (2).pdf史上最全的机器学习面试题-机器学习爱好者必看 (2).pdf史上最全的机器学习面试题-机器学习爱好者必看 (2)...
史上最全的机器学习面试题-机器学习爱好者必看 (2).docx史上最全的机器学习面试题-机器学习爱好者必看 (2).docx史上最全的机器学习面试题-机器学习爱好者必看 (2).docx史上最全的机器学习面试题-机器学习爱好者必看 ...
算法大全-面试题-数据结构.docx
数据库面试题----可以知道数据库面试一般的考试类型及题;数据库面试题----可以知道数据库面试一般的考试类型及题;数据库面试题----可以知道数据库面试一般的考试类型及题;
java私塾面试题----SQL语句
各大公司面试题-中科前程面试题.txt 各大公司面试题-中科前程面试题.txt
最新各大公司企业真实面试题-宝信面试题.txt最新各大公司企业真实面试题-宝信面试题.txt
最新各大公司企业真实面试题-新星公司面试题笔试题最新各大公司企业真实面试题-新星公司面试题笔试题
最新各大公司企业真实面试题-润信科技公司面试题.txt最新各大公司企业真实面试题-润信科技公司面试题.txt最新各大公司企业真实面试题-润信科技公司面试题.txt
c语言面试题----main函数