算法专题:位运算

位运算

Java中的位运算


(一)LeetCode easy

1.【268】missing number

给定一个包含 0, 1, 2, …, n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

  • 示例 1:
    输入: [3,0,1]
    输出: 2

  • 示例 2:
    输入: [9,6,4,2,3,5,7,0,1]
    输出: 8

  • 说明:
    你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

思路

  1. 将数组排序,然后下标和相应位置元素不匹配的第一个下标,就是缺失的元素。但是这种方法时间复杂度是O(NlogN),题目要求线性时间复杂度,即O(N)。
  2. 采用HashMap,遍历数组,每找到一个元素对应的value就+1,这种方法需要额外引进一个HashMap,空间复杂度非常数空间。
  3. 将0-n求和,然后减去数组的和,差就是没有出现的那个数。这种方法的问题是求出的和可能会很大,超过long long的阈值
  4. 可选方案只剩下了位运算:原理是0 ^ b = ba ^ a = 0,那么a ^ a ^ b = b

    0~n的数组:0 1 2 3
    缺失其中某个元素的数组:0 1 3

将两者的所有元素异或:0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 3 ^ 3 = 2,得到的结果就是缺失的元素

  1. 如果遍历入参数组求异或,再遍历0 ~ n求异或,那么我们就需要两次for循环。最好能在1次for循环中完成计算,方法是遍历入参数组(nums[0] ~ nums[len - 1])求异或,同时异或上数组下标(0 ~ (len - 1)),最后额外异或一个len(入参数组是0 ~ n的数组缺少一个元素,所以它的下标最大也只是len - 1,而补上缺失元素的数组长度是len)即可

代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public int missingNumber(int[] nums) {
int len = nums.length;
int xor = len; //初始值为数组长度,即额外异或的那个n
for(int i = 0; i < len; i++) {
xor = xor ^ i ^ nums[i];
}
return xor;
}
}
-------------本文结束感谢您的阅读-------------

本文标题:算法专题:位运算

文章作者:DragonBaby308

发布时间:2019年08月07日 - 07:38

最后更新:2020年01月30日 - 12:54

原始链接:http://www.dragonbaby308.com/Algorithm-BitManipulation/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%