一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 404|回复: 3
收起左侧

[Leetcode] 【single number变体】求好心人讲解这道题的解答

[复制链接] |试试Instant~ |关注本帖
小马3107 发表于 2015-8-30 12:23:03 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目是lintcode上的。
一个整数数组,除了两个元素只有一次重复以外,其他元素都有两次重复。要求是在O(n)复杂度内找出这两个元素,用O(1)空间。
没看明白解答。想知道解答里的
  1. lastBit = xor - (xor & (xor - 1));
复制代码
和第二个 for 循环是什么意思?谢谢!
解答的代码如下:
  1. public class Solution {
  2.     /**
  3.      * @param A : An integer array
  4.      * [url=home.php?mod=space&uid=160137]@return[/url] : Two integers
  5.      */
  6.     public List<Integer> singleNumberIII(int[] A) {
  7.         int xor = 0;
  8.         for (int i = 0; i < A.length; i++) {
  9.             xor ^= A[i];
  10.         }
  11.         
  12.         int lastBit = xor - (xor & (xor - 1));
  13.         int group0 = 0, group1 = 0;
  14.         for (int i = 0; i < A.length; i++) {
  15.             if ((lastBit & A[i]) == 0) {
  16.                 group0 ^= A[i];
  17.             } else {
  18.                 group1 ^= A[i];
  19.             }
  20.         }
  21.         
  22.         ArrayList<Integer> result = new ArrayList<Integer>();
  23.         result.add(group0);
  24.         result.add(group1);
  25.         return result;
  26.     }
  27. }
复制代码
zhuli19901106 发表于 2015-8-30 18:29:36 | 显示全部楼层
lastBit = xor - (xor & (xor - 1));
等效于
lastBit = xor & -xor;

就是树状数组里的lowbit,用于找出一个整数二进制表示里最低位的‘1’。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-8-30 18:30:02 | 显示全部楼层
这个题你可以先搜讲解,把道理弄懂再来看代码
回复 支持 反对

使用道具 举报

xiaozhuge 发表于 2015-9-1 15:29:49 | 显示全部楼层
思路:先全部异或,在得到的结果中找任意一个二进制位为1的位置。根据这个位置的数值的不同,将原数组A分为A1和A2两个数组,即:A1存该位全部为1的元素,A2存该位全部为0的元素。分别将A1和A2异或,得到的结果就是需要寻找的两个single numbers。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 04:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表