位运算

发布： 分类： 评论： 阅读：
1. leetcode 136. Single Number
1
2
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
数组中只有一个数字出现了一次，其他数字都出现了2次。找出这个只出现一次的数字。
  • 异或。相同的两个数二进制异或为0.
  • 所有的元素进行异或，最后的值即为出现一次的元素的值。
1
2
3
4
5
6
public int singleNumber(int[] nums) {
    int res = 0;
    for(int i=0;i<nums.length;i++)
        res = res^nums[i];
    return res;
}
2. leetcode 137. Single Number II
1
2
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
数组中只有一个数字出现了一次，其他数字都出现了3次。找出这个只出现一次的数字。
  • 我们把数组中的每个数字都转为二进制。
  • 如果一个数字出现三次，那么二进制的每一位也都出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别累加起来，那么每一位的和都能被3整除。
  • 那么我们就把所有数字的对应位都累加起来，如果能被3整除，那么出现一次的数字该位为0，否则该位为1，这样运算下来，我们就能知道只出现一次的这个数字的二进制表示，那么我们就可以得到这个数字的值。
1

3. leetcode 260. Single Number III
1
2
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
数组中有两个数字仅出现一次，其余数字都出现两次。找出仅出现一次的这两个数字。
  • 只有一个数字可以直接异或，因为其他部分异或都为0。而两个数字，就不能直接整个数组异或了，因为这两个只出现一次的数字也会求异或，所以得不到两个数字的值。如果能把这两个数字分开，分到两个不同的子数组里就好了。
  • 如何划分到两个不同的子数组中呢？
  1. 假设不同的数字为a和b，
  2. 先将整个数组求异或，那么得到的就是a和b异或的值c
  3. 我们得到c的二进制值，找到第一个为1的位置。该位之所以为1，是因为a和b中只有一个该位置为1，那么我们就能够把a和b区分开了。
  4. 所以，我们假设c的第n位为1，那么我们将整个数组按照第n位是不是为1分成两个数组。那么a和b肯定在不同的数组中
  5. 同时，其他出现两次的每个数字，每个相同的两个数必出现在同一个子数组中，因为他们俩完全相等，第n位是不是1当然也是同样的结果。
  6. 也就是说，两个子数组中，除了a和b分别在自己的子数组中出现一次，其他数字都出现两次，那么我们将两个子数组分别求异或，就能得到a和b的值了。
1