首页 > 试题广场 >

找出缺失的整数

[编程题]找出缺失的整数

热度指数：5212 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个数组number包含了0到n的所有整数，但其中缺失了一个。现规定不能直接取数组number里的数，只能询问数组中第i个元素的二进制的第j位是多少(最低位为第0位)，用A[i][j]表示，且该操作的时间复杂度为常数。已知所有剩下的数按从小到大排列的二进制各位的值，请设计算法，在O(n)时间内返回这个缺失的数。

测试样例：

[[0],[0,1]]

返回：1

算法知识视频讲解

python solution:


class Finder:
    def findMissing(self, numbers, n):
        for i,v in enumerate(numbers):
            if int("".join(map(str,v[::-1])),2)!=i:
                return i
        return n

发表于 2017-11-15 15:31:15 回复(0)

南少201911241210480

class Finder {
public:
    int findMissing(vector<vector<int> > numbers, int n) {
        // write code here
        for(int i=1;i<n;i++)
        {
            if(numbers[i][0]+numbers[i-1][0]!=1)
                return i;
        }
        
    }
};

[[0],[1],[0,1],[1,0],[0,1,1]]每行开头都是01010交替出现，当不是交替出现时比如010110，01001，这都表示11应该是101，变成0101010，或者00要是010，变成010101，所以缺少的数是i

发表于 2020-03-08 12:00:13 回复(0)

胜文

import java.util.*;
public class Finder {
    public int findMissing(int[][] numbers, int n) {
        for(int i=0;i<n-1;i++)
                 //判断这个数的最低位和下一个数的最低位是否相同
            if((numbers[i][0]^numbers[i+1][0])!=1)
               return i+1;
        return n;
    }
}

编辑于 2019-06-04 15:16:36 回复(0)

木然猫猫

理解题意需要的时间远大于解题需要的时间

# -*- coding:utf-8 -*-
class Finder:
    def findMissing(self, numbers, n):
        for i in range(n):
            if i != int(''.join(map(str, numbers[i][::-1])), 2):
                return i
        return n

发表于 2018-12-27 10:12:53 回复(0)

Cavs

只需判断最后一位为0或1即可

class Finder {
public:
    int findMissing(vector<vector<int>> numbers, int n) 
    {
        int miss = 0;
        for(int i = 0;i < n;++i)
        {
            if(i & 1)
            {
                if(numbers[i][0] != 1) return miss;
            }
            else
            {
                if(numbers[i][0] != 0) return miss;
            }
            ++miss;
        }
        return miss;
    }
};

发表于 2017-06-29 15:38:14 回复(0)

Java

村长，那人偷牛！

//我对不起我的语文老师，我真的看不懂题目的意思，想了好久才弄懂题目讲的是啥，我
//相信语文不过关的绝对不止我一个，哈哈哈，在纸上画着画着突然来了灵感，既然是连
//续的，那么肯定是一个奇一个偶数，那么他们的最低位肯定是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)

超小白

  请教大家个问题啊: 我用位运算判断奇偶，if(i&1!=
  numbers[i][0])//i&1不加括号就出问题，是为什么啊  
        intfindMissing(vector<vector<int> > numbers,intn) {  
           inti;  
           for(i=0;i<n;++i){  
               if((i&1) !=
    numbers[i][0])//i&1不加括号就出问题，是为什么啊  
                   break;  
           }  
           returni;  
       }  

发表于 2016-08-28 10:14:07 回复(1)

MichaelTim

class Finder {
public:
    int findMissing(vector<vector<int> > numbers, int n) {
        for(int i = 0; i < n; i++){
            if(i != array2num(numbers[i])) return i;
        }
        return numbers.size();
    }
    int array2num(vector<int> arr){
        int num = 0, delt = 1,size = arr.size();
        for(int i = 0; i < size; i++){
            num += arr[i]*delt;
            delt *= 2;
        }
        return num;
    }
};

发表于 2016-08-23 10:33:10 回复(1)

Python

Yannyezixin

从 0 ~ n如果没有缺失，那个肯定是奇偶交替。缺失了数那么肯定会出现奇数奇数或者偶数偶数的情况

例子： 0 1 2 3 4 5 7, 缺失了6 （判断给出的二进制是奇数或偶数只要看最后一位就可以了，即numbers[i][0]

从0~n遍历， 0 % 2 是否等于 numbers[0][0] ----- 5 % 2 是否等于 numbers[5][0], 6 % 2是否等于numbers[6][0] 发现是缺失了6

# -*- coding:utf-8 -*-
class Finder:
    def findMissing(self, numbers, n):
        #奇偶交替
        for i in range(n):
            if i & 1 != numbers[i][0]:
                return i
        return n

发表于 2016-08-04 08:30:01 回复(0)

Ron

/*A[i][j]含义：表示所有剩余数中，第i个数字的二进制表示的第j位
因此每个数的二进制是按行保存且低位在前，高位在后。
因为是0-N，所以只要判断数之间是否是偶数-奇数交替即可，哪一个数违反了该交替就返回该数
注：其实测试代码中是0-N-1个数进行测试，而非0-N；*/
    public int findMissing(int[][] numbers, int n) {
        // write code here
        for(int i = 0 ; i < n ; i++){
        	if(i % 2 != numbers[i][0]){
        		return i;
        	}
        }
        return n;
    }

编辑于 2015-10-23 10:08:00 回复(0)

字节跳动用户增长客户端团队

如A[0][1]表示剩下的第二个数二进制从低到高的第二位。说的啥玩意啊

题意：每个元素都是二进制位表示，位数从低到高。

例子：[[0],[0,1]]

返回：1

0，2的二进制表示是 0 ，10，将位数从高到低排是，0，01,

然后存成数组的形式就变成[[0],[0,1]]，显然缺失的是1.

编辑于 2015-10-06 21:19:17 回复(2)

manhua

这道题的意思就是给你0~n个整数，vector里存放全是对应整数的二进制，然后要求你找出不连续整数的数值。

发表于 2015-09-26 16:02:17 回复(0)

HelloWorldn

这道简单的题卡我是因为我根本没看懂题目在说什么东西。

发表于 2016-12-16 14:29:49 回复(1)

cdboy

 简要解释下题目:
numbers是一个已经排好序的二维数组，存储的是0-n，但是缺少一个数，每一行存储的是每个数的二进制，从二进制低位开始存储
目标：求缺少的那个数
因为已经是排好序的，所以数字肯定是奇偶不断交替，如果连续碰上奇数奇数则第二个奇数则为缺少的数字，同理偶数也是如此，如果遍历了number数组仍没有找到缺少的数那就是缺少n了。
如有错误，请大家指正

	for(inti = 0; i < n ; i++){



	   if(i % 2!= numbers[i][0])



	     return i;



	return n;

编辑于 2016-01-16 15:54:37 回复(0)

Aurora1

    public int findMissing(int[][] numbers, int n) {
		int i = 0, k = 1 ^ numbers[0][0];
		if (k == 0)
			return 0;
		for (; i < n - 1 && k == 1; i++) {
			k = numbers[i][0] ^ numbers[i + 1][0];
		}
		return k == 1 ? n : i;
	}

发表于 2016-04-09 16:43:35 回复(2)

NewYork

题目已经指明有序，所以可以使用二分搜索，所以，为什么不用呢？

class Finder {
public:
    // O(N)
    int method1(vector<vector<int> > &numbers, int n) {
        for (int i = 0; i < n; i++) {
            if (numbers[i][0] != (i&1)) {
                return i;
            }
        }
        return n;
    }
    
    // O(logN)
    int method2(vector<vector<int> > &numbers, int n) {
    	int low = 0, high = numbers.size()-1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (numbers[mid][0] == (mid&1))
                low = mid + 1;
            else
                high = mid - 1;
        }
        if (low == numbers.size()) return n;
        else return low;
    }
    
    int findMissing(vector<vector<int> > numbers, int n) {
		if (rand() % 2) return method1(numbers, n);
        return method2(numbers, n);
    }
};

发表于 2016-05-24 22:15:13 回复(2)

Java

随机数

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)

嘿，不许笑

写个简单的python二分吧，按理说，，，二分法怎么也该比遍历快的呀，运行出来却慢了点

class Finder:
def findMissing(self, numbers, n):
if numbers[-1][0]==(n-1)%2:return n
l,r,m = 0,n-1,(n-1)//2
while r>l:
if (m%2==0 and numbers[m][0]==0) or (m%2==1 and numbers[m][0]==1):l = m+1
else:r = m
m = (r+l)//2
return m

运行时间：142

内存：5624

发表于 2020-10-13 10:48:56 回复(0)

271828

class Finder {
public:
int findMissing(vector<vector<int> > numbers, int n) {
// write code here
for(int i = 0; i < n-1; i++) {
if(numbers[i][0] == numbers[i+1][0]) {
return i+1;
break;
}
}
return n;
}
};

发表于 2020-08-28 10:28:12 回复(0)