《剑指 Offer》专项突破版 - 面试题 4 : 只出现一次的数字（C++ 实现）-Toy模板网

这篇具有很好参考价值的文章主要介绍了《剑指 Offer》专项突破版 - 面试题 4 : 只出现一次的数字（C++ 实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：137. 只出现一次的数字 II - 力扣（LeetCode）

题目：

输入一个整数数组，数组中只有一个数字出现了一次，而其他数字都出现了 3 次。请找出那个只出现一次的数字。例如，如果输入的数组为 [0, 1, 0, 1, 0, 1, 100]，则只出现一次的数字是 100。

分析：

这个题目有一个简化版的类似的题目 "输入数组中除了一个数字只出现一次之外其他数字都出现两次，请找出只出现一次的数字"。任何一个数字异或它自己的结果都是 0，即 x ^ x = 0。如果将数组中所有数字进行异或运算，那么最终的结果就是那个只出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = nums[0];
        for (int i = 1; i < nums.size(); ++i)
        {
            result ^= nums[i];
        }
        return result;
    }
};

在这个题目中只有一个数字出现了一次，其他数字出现了 3 次。相同的 3 个数字异或的结果是数字本身，即 x ^ x ^ x = x，因此将数组中所有数字进行异或运算并不能消除 3 次的数字，需要想其他办法。

一个整数是由 32 个 0 或 1 组成的。我们可以将数组中所有数字的同一位置的数位相加。

如果数组中所有数字的第 i 个数位相加之和能被 3 整除，那么只出现一次的数字的第 i 个数位一定是 0。

sum 为 0 或 3k（k > 0）。
如果数组中所有数字的第 i 个数位相加之和被 3 除余 1，那么只出现一次的数字的第 i 个数位一定是 1。

sum 为 1 或 1 + 3k（k > 0）。

代码实现：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int i = 0; i < 32; ++i)
        {
            int sum = 0;
            for (int j = 0; j < nums.size(); ++j)
            {
                if (nums[j] & (1 << i))
                    ++sum;
            }

            if (sum % 3 == 1)
                result |= 1 << i;
        }
        return result;
    }
};

举一反三：

题目：

输入一个整数数组，数组中只有一个数字出现 m 次，其他数字都出现 n 次，请找出那个唯一出现 m 次的数字。假设 m 不能被 n 整除。

分析：

如果数组中所有数字的第 i 个数位相加之和能被 n 整除，那么出现 m 次的数字的第 i 个数位一定是 0；否则出现 m 次的数字的第 i 个数位一定是 1。文章来源地址https://www.toymoban.com/news/detail-786714.html

到了这里，关于《剑指 Offer》专项突破版 - 面试题 4 : 只出现一次的数字（C++ 实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！