An array A[1... n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?
首先我们将0到n的所有数字的二进制表达列出来。那么我们可以发现最低位的,大概是这样的情况:count(0)>=count(1)。
如果我们从中移除了一个数字,会怎么样呢?
如果移除的数最低位为0,那么count(1)>=count(0);如果移除的是1,那么count(0)>count(1)。如果n次访问每个数的最低位,那么用以上的准则我们就能判断出没有进入数组的那个数字的最后一位是什么。如果最低位是0的话,那就可以排除最低位为1的元素;如最低位为1,那就可以排除末尾为0的。
那下一步怎么办呢?看次低位的情况?那么我以n=5,未入数组的数字为3。经过上一轮的排除后,剩下的数字如图所示:
那么现在次低位的情况为0 0 1 0 1 0 ,根据之前的逻辑我们知道,次低位应该是1。那么我们继续排除。只保留末尾为11的元素。剩下的就是:
再继续看倒数第三位。同样方法知道第三位应该是0。那么我们确定出了丢失的元素。
根据以上的方法,确定实现代码如下:
那算法的时间复杂是多少呢?第一次扫描了N次的最低位,第二次为N/2......以此类推,根据下式子:
所以我的算法的复杂度为O(n)。
references:
<1> http://article.yeeyan.org/view/9225/175122
<2>cracking the coding interview --Bit Manipulation
分享到:
相关推荐
在 C 语言中,位运算符可以用于实现各种位操作,例如按位与 (&)、按位或 (|)、按位异或 (^)、左移 () 和右移 (>>)。这些运算符可以单独使用,也可以组合使用以实现复杂的位操作。 3. 掩码的应用 掩码是指一个二...
Excel 操作题是初中信息技术考试中的一种常见题型,旨在考察学生对 Excel 软件的操作能力和数据处理能力。 本资源提供了八道 Excel 操作题,每道题目都包含了明确的操作要求,涵盖了 Excel 软件的多种操作功能,如...
文件系统中设置了一张位示图,它是利用二进制的位来表示磁盘中一个块的使用情况。 五、设备管理 设备管理是操作系统中管理计算机硬件设备的部分。CPU 和 I/O 设备之间数据传输的方式有程序 I/O 方式、中断 I/O ...
毕业设计是每位大学生在结束学业时必须完成的重要任务,它通常要求学生综合运用所学知识,独立完成一个项目。在这个“考试系统”毕业设计中,开发者使用了Visual Basic(VB)编程语言,构建了一个适用于Windows操作...
3. 三位数的十位提取:第三题考察了Python中的数字拆分。要获取三位数的十位数字,可以使用整除和取余运算。正确的代码应为`number_2=(number-number//100*100)//10`,这样能从三位数中提取出十位的数字。 4. 赋值...
操作系统是计算机科学中的核心课程,对于考研计算机专业的学生来说,理解和掌握操作系统的基本概念、原理以及应用至关...因此,这份"考研王道操作系统重点习题"是每一位准备考研计算机操作系统的同学必备的学习资源。
本资料包“计算机操作系统练习题”针对操作系统的学习提供了丰富的练习题目,旨在帮助学习者深入理解操作系统的核心概念和原理。 一、操作系统基本概念 1. 定义:操作系统(Operating System,简称OS)是控制计算机...
- 判断水仙花数,水仙花数是指一个三位数,其每一位立方和等于该数本身,如153(1^3 + 5^3 + 3^3 = 153)。通过将输入的数字转换为字符串,再逐位转换回整数并立方求和进行判断。 - 结果显示在`Picture1`中,可能...
计算机操作系统 7套 期末考试题+ 答案详解 吐血上传计算机操作系统 7套 期末考试题+ 答案详解 吐血上传计算机操作系统 7套 期末考试题+ 答案详解 吐血上传计算机操作系统 7套 期末考试题+ 答案详解 吐血上传计算机...
### 计算机高级操作员模拟题知识点解析 #### 一、基础知识 - **计算机系统的组成**:完整的计算机系统由**硬件系统**与**软件系统**两大部分组成。硬件系统包括中央处理器(CPU)、存储器(如RAM和ROM)以及输入/...
同时,"一、选择题(每题2分,共20分).doc"可能是一个综合性的选择题练习,覆盖了多个章节的关键知识点。 总的来说,这些文档是准备操作系统期末考试的重要参考资料,通过深入学习和练习,可以有效地提升你的应试...
1. 对工作表"第一学期期末成绩"中的数据列表进行格式化操作:将第一列"学号"列设为文本,将所有成绩列设为保留两位小数的数值;适当加大行高列宽,改变字体、字号,设置对齐方式,增加适当的边框和底纹以使工作表...
①一个数允许使用的最大数码 ②一个数位允许使用的数码个数 ③一个固定的常数值 ④数码在数据中的不同位置 5.相联存贮器是按( )进行寻址的存贮器。 ① 地址方式 ② 堆栈方式 ③ 内容指定方式 ④ 地址方式与...
- 第4题要求找出一个两位数,十位是3且比个位数小2,这个数是31。 - 第5题是一个简单的加法序列,1到9相加的和是45。 - 第6题中,十位数字比8大,个位数字比1小,所以这个两位数是90。 - 第7题是比例问题,1元能...
Excel 操作练习题知识点总结 本文总结了高中学业水平测试计算机考试 EXCEL 操作练习题中的知识点,涵盖了 Excel 的基本操作、数据处理、图表制作、公式计算等多方面的内容。 一、基本操作 * 合并单元格:使用 ...
这篇资料主要针对小学一年级学生,涉及的数学知识点是两位数减一位数的退位运算,这是基础数学中的减法部分。下面将详细解释这个知识点及其应用。 两位数减一位数的退位运算,通常出现在被减数是个两位数,而减数是...
总的来说,这份练习文档提供了一个有效的工具,帮助孩子在实际操作中熟练掌握100以内两位数加一位数的加法,从而提升他们的数学技能和自信心。同时,家长和教师应鼓励孩子多做练习,并及时给予反馈和指导,以确保...