[数据结构与算法]剑指offer中位运算几题解法

剑指 Offer 15. 二进制中1的个数
题目：
1.编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

解题思路

根据 与运算 定义，设二进制数字 n ，则有：
若 n & 1 = 0，则 n 二进制 最右一位 为 0 ；
若 n & 1 = 1 ，则 nn二进制 最右一位 为 1 。
根据以上特点，考虑以下 循环判断 ：
判断 n 最右一位是否为 11 ，根据结果计数。
将 nn右移一位（本题要求把数字 nn 看作无符号数，因此使用 无符号右移 操作）。
算法流程：
初始化数量统计变量 res = 0。
循环逐位判断： 当 n = 0 时跳出。
res += n & 1 ： 若 n & 1 = 1 ，则统计数 res 加一。
n >>= 1 ： 将二进制数字 nn 无符号右移一位（ Java 中无符号右移为 “>>>” ） 。
返回统计数量 res 。

作者：jyd
链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/solution/mian-shi-ti-15-er-jin-zhi-zhong-1de-ge-shu-wei-yun/

public class Solution {
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
}

剑指 Offer 56 - I. 数组中数字出现的次数
题目：
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

解题思路：

题目要求时间复杂度 O(N) ，空间复杂度 O(1) ，因此首先排除 暴力法 和 哈希表统计法 。

简化问题： 一个整型数组 nums 里除 一个 数字之外，其他数字都出现了两次。

设整型数组 nums中出现一次的数字为 x ，出现两次的数字为 a, a, b, b, …即：

nums = [a, a, b, b, …, x]

异或运算有个重要的性质，两个相同数字异或为 00 ，即对于任意整数 aa 有 a \oplus a = 0a⊕a=0 。因此，若将 numsnums 中所有数字执行异或运算，留下的结果则为 出现一次的数字 xx ，即：
a⊕a⊕b⊕b⊕…⊕x
=0⊕0⊕…⊕x
=x
?
算法流程：
1.遍历 nums执行异或：
设整型数组 nums = [a, a, b, b, …, x, y]，对 nums 中所有数字执行异或，得到的结果为x⊕y ，即：
a⊕a⊕b⊕b⊕…⊕x⊕y
= 0⊕0⊕…⊕x⊕y
= x⊕y
?

2.循环左移计算 mm ：
根据异或运算定义，若整数x⊕y 某二进制位为 11 ，则 xx和 yy的此二进制位一定不同。换言之，找到 x⊕y 某为 1 的二进制位，即可将数组 nums 拆分为上述的两个子数组。根据与运算特点，可知对于任意整数 a 有：
若 a & 0001 = 1，则 aa 的第一位为 1 ；
若 a & 0010 = 1 ，则 aa 的第二位为 1 ；
以此类推……
因此，初始化一个辅助变量 m = 1 ，通过与运算从右向左循环判断，可 获取整数 x⊕y 首位 11 ，记录于 m 中，

3.拆分 nums为两个子数组：

4.分别遍历两个子数组执行异或：
通过遍历判断 nums 中各数字和 m做与运算的结果，可将数组拆分为两个子数组，并分别对两个子数组遍历求异或，则可得到两个只出现一次的数字，代码如下：

作者：jyd
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom/

class Solution {
    public int[] singleNumbers(int[] nums) {
        //定义几个变量，m表示辅助数组
        int x=0,y=0,n=0,m=1;
        //元素之间进行异或运算，得到没有重复元素的两个数字
        for(int num:nums){
            n^=num;
        }
            //m初始是1和任何数&，然后m不断左移，就能不断找到n二进制数中1的位置，也就是m中1的位置。
            while((n&m)==0){
                m<<=1;
            }
        //因为不重复元素不同，所以总有一个位置是一个数为0，另一个数为1，前面m找到了1的位置，这样子与m相与的时候，总是有个是0，有个是1，这样就将两个不同的数分开了
        for(int num:nums){
            if((num&m)!=0){
                x^=num;
            }else{
                y^=num;
            }
        }
        return new int[]{x,y};

    }
}

剑指 Offer 56 - II. 数组中数字出现的次数 II
题目：
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

解题思路：
使用HashMap存储元素，有重复元素，值加一，最后值为1的就是所求

class Solution {
    public int singleNumber(int[] nums) {
    Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int a=nums[i];
            if (map.containsKey(a)){
                map.put(a,map.get(a)+1);
            }else {
                map.put(a,1);
            }
        }
        for (int j=0;j<nums.length;j++){
            int b=nums[j];
            if (map.get(b)==1){
                return b;
            }
        }
       return  -1;
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字
题目：
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

解题思路：
有序数组查找优先想到的就是二分法，然后左右不断遍历即可

class Solution {
    public int missingNumber(int[] nums) {
        int i=0,j=nums.length-1;
        //使用二分法，如果nums(num)!=num，说明num左边不满足条件，否则右边不满足条件
        while(i<=j){
            int m=(i+j)/2;
            if(nums[m]!=m){
                j=m-1;
            }else{
                i=m+1;
            }
        }
        return i;
    }
}

方法2：分情况列举，但是时间复杂度比二分法高

class Solution {
    public int missingNumber(int[] nums) {
        //如果第一个数是1，代表缺失0
        if (nums[0]==1){
            return 0;
        }

        for (int i = 0; i < nums.length; i++) {
             if (nums[i]!=i){
                return i;
            }
        }
        //如果前面都不满足，说明就是一个元素，并且是n
        return nums.length;
    }
}