Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

没辙,智商碾压题。楼主没遇到之前就只会这种做法。

public int singleNumber(int[] A) {
Map<Integer, Integer> counters = new HashMap<>();
for(int i = 0; i < A.length; i++) {
if (!counters.containsKey(A[i])) {
counters.put(A[i], 1);
} else {
counters.put(A[i], counters.get(A[i]) + 1);
}
} for (Integer key : counters.keySet()) {
if (counters.get(key) == 1) {
return key;
}
}
throw new RuntimeException("no single number");
}

而后我们知道可以先声明个长度32的整形数组,int[32]。第i个元素存放“这些整数第i位的1的个数除以三的余数”。好拗口是不是?

public int singleNumber2(int[] A) {
int[] counter = new int[32];
int ret = 0;
for(int i = 0; i < 32; i++) {
for (int j = 0; j < A.length; j++) {
counter[i] += (A[j] >> i) & 1;
}
ret |= (counter[i] % 3) << i;
}
return ret;
}

看了代码其实也不是“不明觉厉”。因为assume只有一个数出现一次,其他都出现3次,那么那个single number的第i位就是余下的那个数。

。。。

楼主中文不好。

btw,还有一个不是很直观的位操作方法。贴这里吧,不过没做过这个的感觉很难想到。

http://oj.leetcode.com/discuss/857/constant-space-solution

最新文章

  1. QQ等级表
  2. C++ 为什么拷贝构造函数参数必须为引用?赋值构造函数参数也必须为引用吗?
  3. IE8兼容H5语义标签
  4. 清除SQLServer日志的两种方法
  5. [设计模式] javascript 之 适配器模式
  6. 18. 4Sum -- 找到数组中和为target的4个数
  7. 图的最短路算法 Bellman-Ford
  8. SSDT Hook
  9. 《OD学HBase》20160814
  10. Foundation框架之NSArray、NSDictionary、NSSet及其Mutable类型
  11. linux mysql 安装(rpm)
  12. python3-day3(函数-返回值)
  13. [Android学习笔记]双缓冲绘图技术
  14. window.requestAnimationFrame() ,做逐帧动画,你值得拥有
  15. install pytorch
  16. 老司机教你在windows不用软件隐藏重要文件
  17. Solr04 - 在Jetty和Tomcat上部署Solr单机服务
  18. 闪动效果的实现 (jquery方式和css方式)以及 keyframes和opacity 与ie等各浏览器兼容问题
  19. ReactiveCocoa入门教程--第二部分
  20. python3学习笔记一(标识符、关键字)

热门文章

  1. virt manager 提示权限不允许(ubuntu)
  2. Win10 下使用 ionic 框架开发 android 应用之搭载开发环境
  3. Entity Framework做IN查询
  4. docker-4 Dockerfile的使用
  5. centos7.2 yum安装lamp环境
  6. Android adb 无线调试
  7. 微信微博分享注意事项(sharesdk)
  8. 【转载】4412开发板、PC、ubuntu通过网线连接
  9. 我的vim配置文件.vimrc
  10. 二分+动态规划 POJ 1973 Software Company