欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Bit Manipulation总结(一)

程序员文章站 2022-05-02 21:46:13
...
位运算这篇文章中已经介绍了关于位运算的一些知识,这里主要介绍leetcode中出现的有关位运算的题目。

有关找单独元素的有三道题,要求空间复杂度为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总结(二)
相关标签: java 位运算