给定一个数组number包含了0到n的所有整数,但其中缺失了一个。现规定不能直接取数组number里的数,只能询问数组中第i个元素的二进制的第j位是多少(最低位为第0位),用A[i][j]表示,且该操作的时间复杂度为常数。已知所有剩下的数按从小到大排列的二进制各位的值,请设计算法,在O(n)时间内返回这个缺失的数。
测试样例:
[[0],[0,1]]
返回:1
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); } };
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
//我对不起我的语文老师,我真的看不懂题目的意思,想了好久才弄懂题目讲的是啥,我 //相信语文不过关的绝对不止我一个,哈哈哈,在纸上画着画着突然来了灵感,既然是连 //续的,那么肯定是一个奇一个偶数,那么他们的最低位肯定是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; }
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; } };
# -*- 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
/*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; }
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;
}
};