给定一个数组number包含了0到n的所有整数，但其中缺失了一个。现规定不能直接取数组number里的数，只能询问数组中第i个元素的二进制的第j位是多少(最低位为第0位)，用A[i][j]表示，且该操作的时间复杂度为常数。已知所有剩下的数按从小到大排列的二进制各位的值，请设计算法，在O(n)时间内返回这个缺失的数。
测试样例：
[[0],[0,1]]
返回：1
[编程题]找出缺失的整数
import java.util.*;
/**
* {
{0} 0的二进制0反着放
{1} 1的二进制1反着放
{0,1} 2的二进制10反着放
{1,1,0} 3的二进制011反着放
{0,0,1} 4的二进制100反着放
{1,0,1} 5的二进制101反着放
... 所以num[i][0]就是每个数二进制的最低位 如果不是,说明这里原本应该有的数缺失了
}
*
**/
public class Finder {
public int findMissing(int[][] numbers, int n) {
for (int i = 0; i < n; i++) {
if (numbers[i][0] != (i & 1)) {
// num[i]本来应该存储i的二进制位的 然而这里的最低位不是i的最低位 说明缺失的就是i
return i;
}
}
return n;
}
}
发表于 2019-03-14 17:44:40
回复(0)
//我对不起我的语文老师，我真的看不懂题目的意思，想了好久才弄懂题目讲的是啥，我
//相信语文不过关的绝对不止我一个，哈哈哈，在纸上画着画着突然来了灵感，既然是连
//续的，那么肯定是一个奇一个偶数，那么他们的最低位肯定是0和1交替的，最低位肯定
//是010101这样交换着来的，/如果我找的一个数，它的最低位和它的下一个数的最低位位
//是一样的，那就说明缺少它+1的数，如/果都是0101交替的，那肯定缺少0或者n，输出的
//时候判断一下就行了，下面是代码，绝对O(n)算法明天看下大神的思路，先睡觉了，不
//能熬夜。。。。
public int findMissing(int[][] numbers, int n) {
if(numbers==null||numbers.length<=0|numbers[9].length<=0||n<=0) return 0;
for(int i=0;i<numbers.length-1;i++){
if((numbers[i][0]^numbers[i+1][0])!=1) return i+1;
}
return numbers[0].length==1&&numbers[0][0]==0?n:0;
}
编辑于 2017-05-14 02:07:48
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
public:
int findMissing(vector<vector<int> > numbers, int n) {
// write code here
for(int i = 0; i < n; i ++)
if(i % 2 != numbers[i][0])
return i;
return n;
}
};