UDN-企业互联网技术人气社区

板块导航

浏览  : 1653
回复  : 1

[小米] 在一个长度为n的整形数组a里,除了三个数字只出现一次外,其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字,程序时间和空间复杂度越小越好。

[复制链接]
忍乳负重的头像 楼主
发表于 2015-5-29 11:07:21 | 显示全部楼层 |阅读模式
在一个长度为n的整形数组a里,除了三个数字只出现一次外,其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字,程序时间和空间复杂度越小越好。
例如:a = {1,3,7,9,5,9,4,3,6,1,7},输出4或5或6
C/C++:
void find(int* a , int n);

Java:
void find(int[] a);

            
发表于 2015-5-29 11:27:27 | 显示全部楼层
  1. int lowbit(int x)
  2. {
  3.     return x&~(x-1);
  4. }
  5.    
  6. void find(int* a , int n)
  7. {
  8.     int i , xors;
  9.     xors = 0;
  10.     for(i = 0 ; i < n ; ++i)
  11.         xors ^= a[i];
  12.         // 三个数两两的异或后lowbit有两个相同,一个不同,可以分为两组
  13.     int fips = 0;
  14.     for(i = 0 ; i < n ; ++i)
  15.         fips ^= lowbit(xors ^ a[i]); // 表示的是:
  16.     flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)
  17.     int b; // 假设三个只出现一次的其中一个数为b
  18.     b = 0;
  19.     for(i = 0 ; i < n ; ++i) {
  20.         if(lowbit(xors ^ a[i]) == fips)
  21.            b ^= a[i];
  22.      } // 成功找到三个数中一个数
  23.      cout<<b<<endl;

  24. }
复制代码

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部