【算法100天 | 10】位运算找出仅出现奇数次的数字系列问题

浅浅的花香味﹌ 2023-09-26 10:52 63阅读 0赞

#### 文章目录 ####

*   *  一、交换数字（LeetCode 面试题 16.01. 交换数字）
     *   *  1、示例
         *  2、思路
         *  3、代码
     *  二、只出现奇数次的数字（LeetCode 136）
     *   *  1、示例
         *  2、思路
         *  3、代码
     *  三、获取一个数二进制位中最右侧的1
     *   *  1、思路
         *  2、代码
     *  四、找出仅出现了奇数次的两个数字
     *   *  1、示例
         *  2、思路
         *  3、代码
     *  五、找到仅出现了K次的数字
     *   *  1、示例
         *  2、思路
         *  3、代码
     *  六、特殊说明

### 一、交换数字（LeetCode 面试题 16.01. 交换数字） ###

[传送链接：面试题 16.01. 交换数字][16.01.]

编写一个函数，不用临时变量，直接交换`numbers = [a, b]`中`a`与`b`的值。

#### 1、示例 ####

**示例：**

> **输入:** numbers = \[1,2\]  
> **输出:** \[2,1\]

**提示：**

*  `numbers.length == 2`
 *  `-2147483647 <= numbers[i] <= 2147483647`

#### 2、思路 ####

一般在做数字交换时，大家都会习惯性的用一个临时变量；但是题目明确声明不许用临时变量。

大家学过位运算的话，应该知道：

>  *  一个数 异或`^` 自己，得到的结果为0；
>  *  一个数和 0 进行 异或`^`，得到的结果为它自己。

所以想交换两个数，可以用多次异或实现。

#### 3、代码 ####

public int[] swapNumbers(int[] numbers) {
        
        // a = a ^ b
        numbers[0] = numbers[0] ^ numbers[1];
        // b = a ^ b ^ b = a
        numbers[1] = numbers[0] ^ numbers[1];
        // a = a ^ b ^ a ^ b ^ b = b
        numbers[0] = numbers[0] ^ numbers[1];
        return numbers;
    }

**执行结果：**

![在这里插入图片描述][08997180d5d948eea32f34c02370dcc9.png]

### 二、只出现奇数次的数字（LeetCode 136） ###

[传送链接：136. 只出现一次的数字][136.]

题干：一个数组中有一个数出现了奇数次，其他数都出现了偶数次，找出这个只出现了奇数次的数；

该题目和`LeetCode 136. 只出现一次的数字`题解完全一样。

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

**说明：**

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

#### 1、示例 ####

**示例 1:**

> **输入:** \[2,2,1\]  
> **输出:** 1

**示例 2:**

> **输入:** \[4,1,2,1,2\]  
> **输出:** 4

#### 2、思路 ####

位运算有如下知识：

>  *  一个数 异或`^` 自己，得到的结果为0；
>  *  一个数和 0 进行 异或`^`，得到的结果为它自己。

因为只有一个数出现了奇数次（1次），其余数都出现了偶数次（2次），所以出现偶数次的数 和自己异或后的结果为0，而出现奇数次的数字 再 和 0 异或 便是它自身。

#### 3、代码 ####

public int singleNumber(int[] nums) {
        
        int eor = 0;
        for (int num : nums) {
        
            eor ^= num;
        }
        return eor;
    }

**执行结果：**

![在这里插入图片描述][10605f278e9b421db210680069502d6f.png]

### 三、获取一个数二进制位中最右侧的1 ###

比如一个数的二进制为： 0110 0100，则获取到的其最右侧的1为： 0000 0100。

#### 1、思路 ####

基于位运算的思想：一个数和它的相反数做与运算，即可得到二进制位中最右侧的1。

比如数字`18`，其二进制为：0001 0010，

其相反数`-18`的二进制为：1110 1110，

它俩做与运算（相同为1，不同为0）的结果为 0000 0010。

#### 2、代码 ####

public static int rightMostOne(int num) {
        
        // 与运算：相同为1，不同为0
        return num & (-num);
    }

### 四、找出仅出现了奇数次的两个数字 ###

一个数组中有两个数出现了奇数次，其他数都出现了偶数次，找到出现奇数次的两个数

#### 1、示例 ####

**示例 1:**

> **输入:** \[2,2,1,3\]  
> **输出:** \[1,3\]

**示例 2:**

> **输入:** \[4,1,2,1,2,7\]  
> **输出:** \[4,7\]

#### 2、思路 ####

首先将所有的数字进行异或运算，得到的结果为仅出现了奇数次的两个数字（`a`、`b`）异或的结果`eor`。

eor的二进制数据中最低位的1代表了a 和 b 二进制数据中开始出现不同的最低位；比如：

> a=4，b=7
> 
>  *  a的二进制为：0100
>  *  b的二进制为：0111
>  *  他们异或的结果为：0011，也就说说他们在第0位上开始出现不同；即：最右位上的1（`rightMost`）为 0001；

所以可以将所有的数字根据`rightMost`分为两类：和rightMost与运算后为0、和rightMost与运算后不为0；这两类数据分别异或后得到的两个数字即为结果。

#### 3、代码 ####

public static int[] findOddTimesNum2(int[] array) {
        
        int eor = 0;
        for (int num : array) {
        
            eor ^= num;
        }
        int rightMost = eor & (-eor);
    
        int oddNum = 0;
        for (int num : array) {
        
            if ((rightMost & num) != 0) {
        
                oddNum ^= num;
            }
        }
        int anotherOddNum = oddNum ^ eor;
        return new int[]{
        oddNum, anotherOddNum};
    }

### 五、找到仅出现了K次的数字 ###

一个数组中，有一个数出现了K次，其他数都出现了M次（M > 1, K < M）；找到仅出现了K次的数；

要求：空间复杂度为O(1)、时间复杂度为O(n)。

#### 1、示例 ####

**示例 1:**

> **输入:** \[2,2,2,3,3,4,4,4\], K=2，M=3  
> **输出:** 3

**示例 2:**

> **输入:** \[2,2,2,2,0,4,4,4,4\], K=1，M=4  
> **输出:** 0

**示例 3:**

> **输入:** \[2,2,2,2,3,3,4,4,4,4\], K=3，M=4  
> **输出:** \-1

#### 2、思路 ####

本题我们无法确定k和m哪个是奇数、哪个是偶数，所以不能单纯使用异或。

也正是因为我们不确定K、M是多少，所以需要记录每个数字出现的次数，但是如果使用HashMap的话，空间复杂度为O(n)，不符合题目要求。所以需要使用其它映射方式，用O(1)的空间复杂度来维护每个数字出现的次数。

因为数字都是整型INT，所以可以采用`bitmap`的思想，用32位来维护每个数字二进制上的1在某一位出现的次数，最后对这32位进行取模（`% M`）运算，即可得到结果数字的每一个二进制位。

#### 3、代码 ####

public static int getOnlyKTimes(int[] array, int k, int m) {
        
        Map<Integer, Integer> indexMap = getIndexMap();
        int[] indexCounts = new int[32];
        int rightMostOne;
        // 特殊数据 0的个数
        int zeroCount = 0;
        // 汇总每个数字的二进制位上的1到indexCounts中，以及num为0的个数。
        for (int num : array) {
        
            if (num == 0) {
        
                zeroCount++;
            }
            while (num != 0) {
        
                rightMostOne = num & (-num);
                indexCounts[indexMap.get(rightMostOne)]++;
                // 查出所有的二进制位1
                num ^= rightMostOne;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
        
            if (indexCounts[i] % m == 0) {
        
                continue;
            }
            if (indexCounts[i] % m == k) {
        
                res |= (1 << i);
            } else {
        
                return -1;
            }
        }
        // 最后检查如果ans为0的特殊场景, 因为indexCounts中没有维护0的个数
        if (res == 0 && zeroCount != k) {
        
            return -1;
        }
        return res;
    }
    
    /**
     * 维护value 和 index的映射， 即 <2^n ,n>
     */
    private static Map<Integer, Integer> getIndexMap() {
        
        Map<Integer, Integer> map = new HashMap<>(64);
        int value = 1;
        for (int i = 0; i < 32; i++) {
        
            map.put(value, i);
            value <<= i;
        }
        return map;
    }

### 六、特殊说明 ###

本文所有题目中的数字全是Int整型；并且为了代码的简洁性，不考虑那些显而易见的边界问题。

[16.01.]: https://leetcode.cn/problems/swap-numbers-lcci/
[08997180d5d948eea32f34c02370dcc9.png]: https://img-blog.csdnimg.cn/08997180d5d948eea32f34c02370dcc9.png
[136.]: https://leetcode.cn/problems/single-number/
[10605f278e9b421db210680069502d6f.png]: https://img-blog.csdnimg.cn/10605f278e9b421db210680069502d6f.png