算法之位运算

巧妙地利用位元算的特性可以以极低的时空复杂度解决问题:squirrel:

1.只出现一次的数字 I

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

思路: 位运算——数组中两两异或即可!

因为有 a ^ a = 0,0 ^ a = a ,并且异或运算满足交换律 故对数组[a,b,c,a,d,d,b] 通过异或运算: a ^ b ^ c ^ a ^ d ^ d ^ b -> a ^ a ^ b ^ b ^ d ^ d ^ c -> 0 ^ 0 ^ 0 ^ c - > c !

2. 只出现一次的数字 II

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

思路:求出每一位和,对3取余即可!

因为只有一个数字出现一次,其他都是三次,说明在每一位上,如果特殊数字出现,那么这一位上 1 的个数一定不是 3 的倍数!相反若其他数字在某位出现而特殊的没有出现,则该位上的 1 的数量一定是 3 的倍数
算法之位运算

 public static int singleNumber (int[] A) {
        // write code here
        if(A == null || A.length == 0){
            return -1;
        }
        int res = 0;
        for(int i = 0;i < 32;i++){ //整数一共32位!所以每一位都得需要统计
            int sum = 0;
            for(int j = 0; j< A.length;j++){ 
                sum += ((A[j] >> i) & 1); //统计第 i 位上 1 的数量
            }
            res += ((sum % 3)<<i); //注意左移i过去的需要右移i回来!!!!
        }
        return res;
    }

延伸一下,对于某数组若只有一个数字出现一次,其他数字都出现 n 次 (n > 1),则都可以通过统计每一位上 1 的数量来做!

3.只出现一次的数字 III

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
输入: [1,2,1,3,2,5]
输出: [3,5]

思路:结合 题目(只出现一次的数字 I) 来做

因为本题有两个数字(假设位a和b)只出现一次,其他都出现两次,所以根据题目一可以马上得到这两个特殊数字的异或结果,即为 a ^ b。之后怎么做?我们知道两数的异或结果代表了两个数字在某些位上的不同!
所以根据这个性质我们可以将该数组分成两部分,这两部分分别只有一个特殊数字!之后分别全部异或一下就得到两个特殊数字!
可以通过 a ^ b 从右开始的第一个出现的 1 所在的 位 作为区分标准!因为这个 1 代表了 a 和 b 在当前位的不同:boom:

public int[] singleNumber(int[] nums) {
        if(nums == null || nums.length <= 1){
            return new int[]{};
        }
        int xor = 0;
        for(int n : nums){
            xor ^= n; //求出两数的异或
        }
        int bit = 1;
        while((xor & 1) == 0){
            //从左往右寻找第一个 1
            xor >>=1;
            bit <<= 1;
        }
        int val1 = 0;
        int val2 = 0;
        for(int n : nums){
            if((n & bit) == 0){ //如果和当前bit位相同,则归为一类
                val1 ^= n;
            }else{ //否则归为另一类
                val2 ^= n;
            }
        }
        return new int[]{val1,val2};
    }
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!