剑指 Offer 56 - II. 数组中数字出现的次数 II

问题描述

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

 

示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

 

限制：

• 1 <= nums.length <= 10000
• 1 <= nums[i] < 2^31

 

解题思路

只有当某一位上 \(1\) 出现 \(3n+1\) 次时，该位置才为 \(1\)，否则为 \(0\)。

用 \(x\) 表示当前数字的某一位，\(a_1,a_0\) 分别记录 \(1\) 出现的次数，\(y\) 表示该位最终的值。所以可以写出下面的真值表。

\[ \begin{array}{|cc|c||cc||c|} \hline a_1 & a_0 & x & a_1 & a_0 & y\\\hline 0&0&0&0&0&0\\ 0&0&1&0&\boxed{1}&1\\ 0&1&0&0&\boxed{1}&1\\ 0&1&1&\boxed{1}&0&0\\ 1&0&0&\boxed{1}&0&0\\ 1&0&1&\boxed{1}&\boxed{1}&0\\ 1&1&0&\boxed{1}&\boxed{1}&0\\ 1&1&1&0&\boxed{1}&1\\\hline \end{array} \]

根据真值表有：

\[ \begin{aligned} a_1 &= \bar{a_1}a_0x+a_1\bar{a_0}\bar{x}+a_1\bar{a_0}x+a_1a_0\bar{x}\\ a_0&=\bar{a_1}\bar{a_0}x+\bar{a_1}a_0\bar{x}+a_1\bar{a_0}x+a_1a_0\bar{x}+a_1a_0x\\ y&=\bar{a_1}a_0 \end{aligned} \]

所以可以根据真值表来迭代，也可以用 卡诺图 化简后再进行计算。这里给出没化简的代码。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a1 = 0, a0 = 0;
        for (int x : nums) {
            int b1 = ~a1&a0&x | a1&~a0&~x | a1&~a0&x | a1&a0&~x;
            int b0 = ~a1&~a0&x | ~a1&a0&~x | a1&~a0&x | a1&a0&~x | a1&a0&x;
            a1 = b1, a0 = b0;
        }
        return ~a1&a0;
    }
};

返回顶部

在手机上阅读