如何找到数组中出现指定次数的数字?

r囧r小猫 2023-09-27 20:24 8阅读 0赞

## 问题一 ##

一个数组中有一种数出现了奇数次, 其他数都出现了偶数次, 怎么找到这个种数?

在线OJ: [LeetCode136. 只出现一次的数字][LeetCode136.]

解题思路:

因为 `a ^ a = 0`, 所以出现过偶次的数异或结果都是 `0`, 又因为 `0^a=a`, 所以把数组中所有的数进行`异或`以后的结果, 就是出现了奇数次的那个数.

代码实现:

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

## 问题二 ##

一个数组中有两种数出现了奇数次, 其他数都出现了偶数次, 怎么找到这两种数.

在线OJ: [LeetCode260. 只出现一次的数字 III][LeetCode260. _ III]

根据问题一的结论, 假设数组中 `a` 和 `b` 这两个数出现了奇数次, 这个数组中的所有数字异或以后得到的结果一定 `a^b`, 但因为 `a` 和 `b` 是两种不同的数, 所以 `a^b` 的结果一定不等于 `0`.

所以, `a^b` 的结果如果转换成二进制的话, **一定至少有一个二进制位是 1**.

我们假设 `a^b` 转换成二进制后最右侧位置的 `1` 在 `i` 位置, 由此可以得出一个结论: **a 和 b 的二进制在i位置一定一个为 0, 一个为 1.**

不妨假设 `a` 的 `i` 位置为 0, `b` 的 `i` 位置为 `1`.

此外, 容易得知, 整个数组中的数, `i` 位置为 0 的数除了 `a` 以外, 其他数一定有偶数个, i 位置为 1 的数除了 `b` 之外, 其他数一定有偶数个.

那么我们可以**只对** `i` 位置为 1 的数求异或, 最后得到的值一定是 `b`, 然后通过 `b^(a^b) = a`, 可以得到 `a` 的值.

最后只剩下一个问题: **如何求一个数只有其最右侧的1对应的的数呢?**

假设某个数x二进制为: `00010010`, 那么其只有最右侧的 1 对应的数就是: `00000010`.

算法是: 对于一个数 `x` 来说, 其只有最右侧的 1 对应的数等于 `x & ((~x) + 1)` 或者 `x & (-x)`.

所以, 如果一个数是 `a^b`, 那么它只有最右侧的1对应的数就是 `(a^b) & (~(a^b) + 1)`.

我们用 `(a^b) & (~(a^b) + 1)` 这个值去和数组中每个值进行与运算, 如果与完以后的结果是 0, 说明这个数 i 位置是 0, 否则说明这个数 `i` 位置是1; 我们前面已经得到一个结论, `i` 位置为0的数除了 `a` 以外, 其他数一定有偶数个; 所以, 用 `(a^b) & (~(a^b) + 1)` 这个值和每个 `i` 位置是 0 的数组元素做与运算以后, 最后的结果一定是 `a`; 得到 `a` 以后, 然后通过 `a^(a^b) = b`, 可以得到 `b` 的值.

代码实现:

class Solution {
        
        public int[] singleNumber(int[] arr) {
        
            int ret = 0;
            for (int num : arr) {
        
                ret ^= num;
            }
            // 此时ans的结果是 a ^ b 的结果
            // 随便提取出 ans 随便哪一位置的 1 进行之后过程
            // 因为 a ^ b 的结果的这一位置为1, 那么这两个数的这一二进制位置一定不不同, 就可以以此进行区分
            // 一个数 & 上 它的相反数(取反+1)就可以可以提取出它最右侧的 1, 其余二级制位为0
            int rightOne = ret & (-ret);
    
            int ans1 = 0;
            for (int num : arr) {
        
                if ((num & rightOne) != 0) {
        
                    ans1 ^= num;
                }
            }
            int ans2 = ret ^ ans1;
    
            return new int[] {
        ans1, ans2};
        }
    }

当有了如下公式可以计算一个数最右侧的 `1` 以后, 也可以完成这样一个题

x & ((~x) + 1)

在线OJ: [LeetCode191. 位1的个数][LeetCode191. _1]

解题思路:

可以使用上面的公式提取出最右侧的 `1` 以后, 与目标数进行或运算, 得到一个新的目标数, 然后继续提取新目标数的最右侧的 `1`, 如此往复, 直到目标值为 `0`, 即可把所有位置的 `1` 都提取出来.

代码实现:

public class Solution {
        
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
        
            if (n == 0) {
        
                return 0;
            }
            int count = 0;
            int rightOne = 0;
            while (n != 0) {
        
                rightOne = n & (-n);
                count++;
                n ^= rightOne;
            }
            return count;
        }
    }

## 问题三 ##

一个数组中有一种数出现 k 次, 其他数都出现了 m 次 (m > 1, k < m), 找到出现了 k 次的数.

要求: **假设数组中所有数都是 int 类型, 额外空间复杂度 O(1), 时间复杂度 O(N).**

在线OJ: [LeetCode137. 只出现一次的数字 II][LeetCode137. _ II]

我们可以这样考虑, 设置一个 32 位的数组,

int[] help = new int[32];

遍历原始数组中每个数 num 的每一个二进制位, 伪代码如下：

for (int num : arr) {
        
      for (int i = 0; i < 32; i++) {
        
        help[i] += num的二进制中i位置的值(只能是0或者1)
      }
    }

经过以上循环, `help` 数组就把数组中的所有数的二进制位上的信息累加起来了;

`help[0]` 表示数组中所有数二进制中0位置的值之和;

`help[1]` 表示数组中所有数二进制中1位置的值之和;

…

`help[31]` 表示数组中所有数二进制中31位置的值之和.

然后 `i` 从 `0` 位置开始拿出 `help[i]` 的值, 假设 `help[i]=x`, 用 `x % m`, 如果结果是 `k`, 说明出现 `k` 次的元素在这个位置上是 1, 否则, 这个出现了 `k` 次的数在 `i` 位置上是 `0`, 遍历完 `help` 数组, 出现 `k` 次元素的每一位信息都拿到了, 然后还原出来即可.

通用代码:

/*一个数组中有一种数出现K次，其他数都出现了M次，
    已知M > 1，K < M，找到出现了K次的数, 如果不存在出现了K次的数, 返回-1
    要求额外空间复杂度O(1)，时间复杂度O(N)*/
    public static int onlyKTimes(int[] arr, int k, int m) {
        
        // 用来将 arr 数组中元素相应位置二进制位为 1 的个数
        int[] help = new int[32];
        // 遍历arr数组
        for(int num : arr) {
        
            // 将每一个元素二进制为 1 的个数进行累加
            for (int i = 0; i <= 31; i++) {
        
                // 判断每一位二进制位值是否为 1
                if (((num >> i) & 1) != 0) {
        
                    // 为 1 就累加到相应位置
                    help[i]++;
                }
                // 这个判断和 help[i] += (num >> i) & 1 等效
            }
        }
        int ans = 0;
        // 如果出现 m 次元素中的某个二进制位为 1, 那么 help 数组中相应位置的累加和一定是 m 的倍数
        // 如果出现 k 次元素中某个二进制为 1, 出现 m 次元素中的这个二进制位也为 1, 那么 help 数组中相应位置的累加和一定不能被 m 整数
        // 出现的不是 k 次, 但要比 m 小, 也是不能被 m 整除的, 返回-1
        for (int i = 0; i < 32; i++) {
        
            if (help[i] % m == 0) {
        
                continue;
            }
            // 如果找到了不能被 m 整除的, 等于k, 那么说明结果中这个二进制位一定是为 1 的
            // 不等于k, 那么除了出现 m 次的元素, 剩下的这个元素就不是出现 k 次的, 返回 -1 即可
            if (help[i] % m == k) {
        
                ans |= (1 << i);
            } else {
        
                return -1;
            }
        }
        // 出现 k 次的元素如果是0的话, 上面的遍历就会一直 continue, 就没有判断的时机了
        // 所以这里对于 0 的情况需要特殊判断一下
        if (ans == 0) {
        
            int count = 0;
            for (int num : arr) {
        
                if (num == 0) {
        
                    count++;
                }
            }
            if (count != k) {
        
                return -1;
            }
        }
    
        // 如果题意是数组中出现 k 的数字一定存在, 可以换成下面的代码
        /*for (int i = 0; i < 32; i++) {
            if (help[i] % m != 0) {
                ans |= (1 << i);
            }
        }*/
    
        return ans;
    }

解题代码:

class Solution {
        
        public int singleNumber(int[] arr) {
        
            int[] help = new int[32];
            for(int num : arr) {
        
                for (int i = 0; i <= 31; i++) {
        
                    if (((num >> i) & 1) != 0) {
        
                        help[i]++;
                    }
                }
            }
            int ans = 0;
            for (int i = 0; i < 32; i++) {
        
                if (help[i] % 3 != 0) {
        
                    ans |= (1 << i);
                }
            }
            if (ans == 0) {
        
                int count = 0;
                for (int num : arr) {
        
                    if (num == 0) {
        
                        count++;
                    }
                }
            }
            return ans;
        }
    }

[LeetCode136.]: https://leetcode.cn/problems/single-number/
[LeetCode260. _ III]: https://leetcode.cn/problems/single-number-iii/
[LeetCode191. _1]: https://leetcode.cn/problems/number-of-1-bits/
[LeetCode137. _ II]: https://leetcode.cn/problems/single-number-ii/