Bit Manipulation总结(一)
程序员文章站
2022-05-02 21:46:13
...
在位运算这篇文章中已经介绍了关于位运算的一些知识,这里主要介绍leetcode中出现的有关位运算的题目。
有关找单独元素的有三道题,要求空间复杂度为O(n),空间复杂度为O(1),我们都可以通过位运算来解决。
1,Single Number
给定一个数组,每个元素都出现了两次,只有一个元素出现了一次,找出这个元素.
我们将所有的元素进行异或操作,最终的结果就是单独的元素,相同元素异或为0. 代码如下:
2,Single Number II
给定一个数组,每个元素都出现了三次,只有一个元素出现了一次,找出这个元素。
我们将数组中每个元素都按位操作,通过一个长度为32的数组记录每个位置上1的个数,然后通过与3取余,结果就为单独的元素。代码实现如下:
3,Single Number III
给定一个数组,每个元素都出现了两次,有两个元素只出现了一次,找出这两个元素。
解决这道题的办法是我们将数组中所有元素进行异或操作,得到一个数字,这个数字为1的位置,代表要找的两个数在这个位置的数字不同,肯定一个为0,一个为1。我们可以取其中一个1,将数组元素依次与它位与&,结果为0的分到一组,结果为1的分到一组,这样我们可以把数组划分为两部分,这两个数分别在不同的组,具体代码实现如下:
4,Missing Number
给定一个包含n个数的不含重复元素的数组,元素的范围为0....n,找出数组没有包含的那个元素。
例如:给定 nums[] = {0, 1, 3} 输出:2
将数组里的元素异或,再将结果与0....n异或,结果就是缺少的元素。代码如下:
接下篇 Bit Manipulation总结(二)
有关找单独元素的有三道题,要求空间复杂度为O(n),空间复杂度为O(1),我们都可以通过位运算来解决。
1,Single Number
给定一个数组,每个元素都出现了两次,只有一个元素出现了一次,找出这个元素.
我们将所有的元素进行异或操作,最终的结果就是单独的元素,相同元素异或为0. 代码如下:
public class Solution { public int singleNumber(int[] nums) { int result = 0; for(int i = 0; i < nums.length; i++) { result ^= nums[i]; } return result; } }
2,Single Number II
给定一个数组,每个元素都出现了三次,只有一个元素出现了一次,找出这个元素。
我们将数组中每个元素都按位操作,通过一个长度为32的数组记录每个位置上1的个数,然后通过与3取余,结果就为单独的元素。代码实现如下:
public class Solution { public int singleNumber(int[] nums) { int[] digits = new int[32]; int result = 0; int mask = 1; for(int i = 0; i < 32; i++) { for(int j = 0; j < nums.length; j++) { if((mask & (nums[j] >> i)) == 1) { digits[i] ++; } } result |= (digits[i] % 3) << i; } return result; } }
3,Single Number III
给定一个数组,每个元素都出现了两次,有两个元素只出现了一次,找出这两个元素。
解决这道题的办法是我们将数组中所有元素进行异或操作,得到一个数字,这个数字为1的位置,代表要找的两个数在这个位置的数字不同,肯定一个为0,一个为1。我们可以取其中一个1,将数组元素依次与它位与&,结果为0的分到一组,结果为1的分到一组,这样我们可以把数组划分为两部分,这两个数分别在不同的组,具体代码实现如下:
public class Solution { public int[] singleNumber(int[] nums) { int helper = 0; for(int i = 0; i < nums.length; i++) { helper ^= nums[i]; } int tell = helper & (~(helper - 1)); int single1 = 0; int single2 = 0; for(int j = 0; j < nums.length; j++) { if((nums[j] & tell) == 0) single1 ^= nums[j]; else single2 ^= nums[j]; } int[] result = {single1, single2}; return result; } }
4,Missing Number
给定一个包含n个数的不含重复元素的数组,元素的范围为0....n,找出数组没有包含的那个元素。
例如:给定 nums[] = {0, 1, 3} 输出:2
将数组里的元素异或,再将结果与0....n异或,结果就是缺少的元素。代码如下:
public class Solution { public int missingNumber(int[] nums) { int result = 0; for(int i = 0; i < nums.length; i++) { result ^= i ^ nums[i]; } return result ^ nums.length; } }
接下篇 Bit Manipulation总结(二)