首页 > 试题广场 >

找出缺失的整数

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

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

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

测试样例：

[[0],[0,1]]

返回：1

算法知识视频讲解

推荐

九城城主

    题目：  

    numbers是一个已经排好序的二维数组，存储的是0-n，但是缺少一个数，每一行存储的是每个数的  

    二进制，从二进制低位开始存储。  

    目标：求缺少的那个数

思路：整数值x的二进制表示最低位为1的时候，x为奇数；最低位为0时，x为偶数。

由于数组中的数是0~n剩余数按照从小到大进行排列的，因此在缺失数之前，数组行标与数是相等的，即行标i = x，此时行标i % 2的值与数组中numbers[i][0]是相等的，即i为奇数，numbers[i][0]为1；为偶数时，numbers[i][0]为0.

第一个 i % 2与numbers[i][0]不相等处即为缺失数。

要注意缺失数为n即最大值的情况。要单独return n；

代码如下所示：

class Finder {
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;
    }
};

编辑于 2016-01-18 12:50:31 回复(21)

Python

华科平凡

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)

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)