校园招聘

小米科技

北京小米科技有限责任公司

所属行业:互联网/电子商务 企业性质:私营/民营企业 企业规模:1000人以上

小米技术岗位笔试题

时间:2016-11-30 编辑:光辉

  题目:一个数组里,除了三个数是唯一出现的,其余的都出现偶数个,找出这三个数中的任一个。比如数组元素为【1, 2,4,5,6,4,2】,只有1,5,6这三个数字是唯一出现的,我们只需要输出1,5,6中的一个就行。

  下面是我的解法,找到三个数字一个数的第一个bit位(这里是从右到左算)和其它二个不一样的数就行

  如1,5,6的二进制分别为0001,0101,0110。因为6的的第一位为0,而其他的为1,用我的程序第一个输出的就是6了。程序如下:

  view plaincopyprint?

  #include

  //得到第i位的二进制

  #define isON(n, i) ((n)  1 << (i))

  // Author: 397090770

  // E-mail: wyphao.2007@163.com

  // 转载请注明出处

  void findTheSingleNumber(int *arr, int size){

  int tempA = 0, tempB = 0;

  int countA = 0, countB = 0;

  int i = 0, j = 0;

  for(i = 0; i < 31; i++){ //32位平台上,int只有32位

  tempA = tempB = countA = countB = 0;

  for(j = 0; j < size; j++){//遍历数组

  if(isON(arr , i)){

  tempA ^= arr ;

  countA++;

  }else{

  tempB ^= arr ;

  countB++;

  }

  }

  if(countA  0x1){//奇数

  if(0 == tempB){

  continue;

  }else{

  printf("%d ", tempA);//肯定是不同的数字

  break;

  }

  }else{

  if(0 == tempA){

  continue;

  }else{

  printf("%d ", tempB);

  break;

  }

  }

  }

  }

  int main(){

  int arr = {

  /*1, 3, -9, 2, 1, 2, -10*/

  1, 2,4,5,6,4,2

  };

  findTheSingleNumber(arr, sizeof(arr) / sizeof(arr ));

  return 0;

  }

  时间复杂度为O(N)。输出为 6。(如果要全部输出不同的数,方法和上面的一样)

  哪位大牛还有别的解法吗?

  另附:第一大题为求最大子序列。上面那题为第二大题。

您需要登录后才可以回帖登录|注册
发布

互联网/电子商务

私营/民营企业

1000人以上

http://www.xiaomi.com/

公司地址

北京市 - 北京市 - 海淀区清河中街68号 华润五彩城写字楼

扫码关注官方微信

及时获取"最新"校招信息