只出现一次的数字 II（ LeetCode 137 ）

一、题目描述

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

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

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 104
• -2^31 <= nums[i] <= 2^31 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

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

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 只出现一次的数字 II（ LeetCode 137 ）:https://leetcode-cn.com/problems/single-number-ii
class Solution {
    public int singleNumber(int[] nums) {

        // 设置一个长度为 32 位的数组
        // 在这个数组中，每一位存储的就是 nums 数组中每一位二进制形式相加后 1 的个数
        int[] cnt = new int[32];

        // 遍历 nums 数组
        // 虽然这里有两个 for 循环，但是内层循环的 n 是常数，因此时间复杂度依旧为 O(n)
        for (int i = 0 ; i < nums.length ; i++ ) {

            // 获取第 i 位的数字
            int num = nums[i];

            // 将 num 展开为二进制的形式，有 32 位
            for (int j = 0; j < 32; j++) {


                // >> 表示右移符号，右移运算是将一个二进制位的操作数按指定移动的位数向右移动，移出位被丢弃
                // >> j 表示右移了 j 位
                // 比如 num 的二进制表示为 
                // 0000 0000 0000 0000 0000 0000 0000 0010
                // >> 1 之后变成了
                // _000 0000 0000 0000 0000 0000 0000 0001
                // _ 在计算机中默认为 0 ，所以结果就是 0000 0000 0000 0000 0000 0000 0000 0001
                int temp = num >> j;


                // & 表示按位与运算符，只有对应的两个二进位都为 1 时，结果位才为 1
                // 每次将 num 向右移动之后，都将移动后的数和 1 进行按位与操作
                // 这样就得到了 num 中第 i 个二进制位
                // 比如 num 的二进制表示为 
                // 0000 0000 0000 0000 0000 0000 0000 0010
                // 当 j = 0 时，temp 为
                // 0000 0000 0000 0000 0000 0000 0000 001【0】 // temp 的二进制表示
                // &
                // 0000 0000 0000 0000 0000 0000 0000 000【1】 // 1 的二进制表示
                // =
                // 0000 0000 0000 0000 0000 0000 0000 000【0】 // 等于 0
                // 即 num 的第 0 个位置的二进制位 0
                // < -------------->
                // 当 j = 1 时，temp 为
                // 0000 0000 0000 0000 0000 0000 0000 000【1】 // temp 的二进制表示
                // &
                // 0000 0000 0000 0000 0000 0000 0000 000【1】 // 1 的二进制表示
                // =
                // 0000 0000 0000 0000 0000 0000 0000 000【1】 // 等于 1
                // 即 num 的第 1 个位置的二进制位 1
                int x = temp & 1;

                // 如果第 j 位的二进制位是 1，把它累加到 cnt[j] 上
                // cnt[j] 表示 nums 数组中每一个数字二进制形式表示后，第 j 位有多少个 1
                if ( x == 1) {
                    cnt[j]++;
                }
            }

        }

        // 使用 ans 用来记录 nums 中那个只出现了一次的元素
        // 一开始 ans 的二进制表示为 
        // 0000 0000 0000 0000 0000 0000 0000 0000 
        // 即由 32 个 0 组成
        int ans = 0;

        // 此时，cnt 已经存储的 nums 数组中每一位二进制形式相加后 1 的个数
        // 遍历每个位置
        for (int i = 0; i < 32; i++) {

            // 因为相同数字的二进制表示是一样的，也就意味着如果它出现了三次，那么这个数字相加三次之后，
            // 在某个位置上出现 1 的次数要么是 0 次，要么是 3 次
            // 比如数字 2，它的二进制是  0000 0000 0000 0000 0000 0000 0000 00【1】0
            // 出现三次时，【1】 也必然出现三次
            // 将某个位置相加的结果除以 3，如果余数为 1，表明只出现了一次
            int temp = cnt[i] % 3;

            // 把出现了一次的二进制位添加到 ans 上
            if (temp == 1) {

                // << 表示左移符号，用来将一个数的各二进制位全部左移若干位
                // 移动的位数由右操作数指定，右操作数必须是非负值，其右边空出的位用 0 填补，高位左移溢出则舍弃该高位
                // 这个操作就是不断的填充二进制
                int num = 1 << i;

                // 把二进制结果累加到 ans 上
                ans += num;
            }
        }

        // 返回 ans 就行
        return ans;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 只出现一次的数字 II（ LeetCode 137 ）:https://leetcode-cn.com/problems/single-number-ii
class Solution {
public:
    int singleNumber(vector<int>& nums) {

        // 设置一个长度为 32 位的数组
        // 在这个数组中，每一位存储的就是 nums 数组中每一位二进制形式相加后 1 的个数
        vector<int> cnt(32, 0);

        // 遍历 nums 数组
        // 虽然这里有两个 for 循环，但是内层循环的 n 是常数，因此时间复杂度依旧为 O(n)
        for (int i = 0 ; i < nums.size() ; i++ ) {

            // 获取第 i 位的数字
            int num = nums[i];

            // 将 num 展开为二进制的形式，有 32 位
            for (int j = 0; j < 32; j++) {


                // >> 表示右移符号，右移运算是将一个二进制位的操作数按指定移动的位数向右移动，移出位被丢弃
                // >> j 表示右移了 j 位
                // 比如 num 的二进制表示为 
                // 0000 0000 0000 0000 0000 0000 0000 0010
                // >> 1 之后变成了
                // _000 0000 0000 0000 0000 0000 0000 0001
                // _ 在计算机中默认为 0 ，所以结果就是 0000 0000 0000 0000 0000 0000 0000 0001
                int temp = num >> j;


                // & 表示按位与运算符，只有对应的两个二进位都为 1 时，结果位才为 1
                // 每次将 num 向右移动之后，都将移动后的数和 1 进行按位与操作
                // 这样就得到了 num 中第 i 个二进制位
                // 比如 num 的二进制表示为 
                // 0000 0000 0000 0000 0000 0000 0000 0010
                // 当 j = 0 时，temp 为
                // 0000 0000 0000 0000 0000 0000 0000 001【0】 // temp 的二进制表示
                // &
                // 0000 0000 0000 0000 0000 0000 0000 000【1】 // 1 的二进制表示
                // =
                // 0000 0000 0000 0000 0000 0000 0000 000【0】 // 等于 0
                // 即 num 的第 0 个位置的二进制位 0
                // < -------------->
                // 当 j = 1 时，temp 为
                // 0000 0000 0000 0000 0000 0000 0000 000【1】 // temp 的二进制表示
                // &
                // 0000 0000 0000 0000 0000 0000 0000 000【1】 // 1 的二进制表示
                // =
                // 0000 0000 0000 0000 0000 0000 0000 000【1】 // 等于 1
                // 即 num 的第 1 个位置的二进制位 1
                int x = temp & 1;

                // 如果第 j 位的二进制位是 1，把它累加到 cnt[j] 上
                // cnt[j] 表示 nums 数组中每一个数字二进制形式表示后，第 j 位有多少个 1
                if ( x == 1) {
                    cnt[j]++;
                }
            }

        }

        // 使用 ans 用来记录 nums 中那个只出现了一次的元素
        // 一开始 ans 的二进制表示为 
        // 0000 0000 0000 0000 0000 0000 0000 0000 
        // 即由 32 个 0 组成
        int ans = 0;

        // 此时，cnt 已经存储的 nums 数组中每一位二进制形式相加后 1 的个数
        // 遍历每个位置
        for (int i = 0; i < 32; i++) {

            // 因为相同数字的二进制表示是一样的，也就意味着如果它出现了三次，那么这个数字相加三次之后，
            // 在某个位置上出现 1 的次数要么是 0 次，要么是 3 次
            // 比如数字 2，它的二进制是  0000 0000 0000 0000 0000 0000 0000 00【1】0
            // 出现三次时，【1】 也必然出现三次
            // 将某个位置相加的结果除以 3，如果余数为 1，表明只出现了一次
            int temp = cnt[i] % 3;

            // 把出现了一次的二进制位添加到 ans 上
            if (temp == 1) {

                // << 表示左移符号，用来将一个数的各二进制位全部左移若干位
                // 移动的位数由右操作数指定，右操作数必须是非负值，其右边空出的位用 0 填补，高位左移溢出则舍弃该高位
                // 这个操作就是不断的填充二进制
                int num = 1 << i;

                // 把二进制结果累加到 ans 上
                ans += num;
            }
        }

        // 返回 ans 就行
        return ans;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 只出现一次的数字 II（ LeetCode 137 ）:https://leetcode-cn.com/problems/single-number-ii
class Solution:
    def singleNumber(self, nums: List[int]) -> int:

        # 设置一个长度为 32 位的数组
        # 在这个数组中，每一位存储的就是 nums 数组中每一位二进制形式相加后 1 的个数
        cnt = [0] * 32

        # 遍历 nums 数组
        # 虽然这里有两个 for 循环，但是内层循环的 n 是常数，因此时间复杂度依旧为 O n)
        for  i in range(len(nums)) : 

            # 获取第 i 位的数字
            num = nums[i]

            # 将 num 展开为二进制的形式，有 32 位
            for j in range(32) : 


                # >> 表示右移符号，右移运算是将一个二进制位的操作数按指定移动的位数向右移动，移出位被丢弃
                # >> j 表示右移了 j 位
                # 比如 num 的二进制表示为 
                # 0000 0000 0000 0000 0000 0000 0000 0010
                # >> 1 之后变成了
                # _000 0000 0000 0000 0000 0000 0000 0001
                # _ 在计算机中默认为 0 ，所以结果就是 0000 0000 0000 0000 0000 0000 0000 0001
                temp = num >> j


                # & 表示按位与运算符，只有对应的两个二进位都为 1 时，结果位才为 1
                # 每次将 num 向右移动之后，都将移动后的数和 1 进行按位与操作
                # 这样就得到了 num 中第 i 个二进制位
                # 比如 num 的二进制表示为 
                # 0000 0000 0000 0000 0000 0000 0000 0010
                # 当 j = 0 时，temp 为
                # 0000 0000 0000 0000 0000 0000 0000 001【0】 # temp 的二进制表示
                # &
                # 0000 0000 0000 0000 0000 0000 0000 000【1】 # 1 的二进制表示
                # =
                # 0000 0000 0000 0000 0000 0000 0000 000【0】 # 等于 0
                # 即 num 的第 0 个位置的二进制位 0
                # < -------------->
                # 当 j = 1 时，temp 为
                # 0000 0000 0000 0000 0000 0000 0000 000【1】 # temp 的二进制表示
                # &
                # 0000 0000 0000 0000 0000 0000 0000 000【1】 # 1 的二进制表示
                # =
                # 0000 0000 0000 0000 0000 0000 0000 000【1】 # 等于 1
                # 即 num 的第 1 个位置的二进制位 1
                x = temp & 1

                # 如果第 j 位的二进制位是 1，把它累加到 cnt[j] 上
                # cnt[j] 表示 nums 数组中每一个数字二进制形式表示后，第 j 位有多少个 1
                if   x == 1 :
                    cnt[j] += 1





        # 使用 ans 用来记录 nums 中那个只出现了一次的元素
        # 一开始 ans 的二进制表示为 
        # 0000 0000 0000 0000 0000 0000 0000 0000 
        # 即由 32 个 0 组成
        ans = 0

        # 此时，cnt 已经存储的 nums 数组中每一位二进制形式相加后 1 的个数
        # 遍历每个位置
        for  i in range(32) :

            # 因为相同数字的二进制表示是一样的，也就意味着如果它出现了三次，那么这个数字相加三次之后，
            # 在某个位置上出现 1 的次数要么是 0 次，要么是 3 次
            # 比如数字 2，它的二进制是  0000 0000 0000 0000 0000 0000 0000 00【1】0
            # 出现三次时，【1】 也必然出现三次
            # 将某个位置相加的结果除以 3，如果余数为 1，表明只出现了一次
            temp = cnt[i] % 3

            # 把出现了一次的二进制位添加到 ans 上
            if  temp == 1 :

                # << 表示左移符号，用来将一个数的各二进制位全部左移若干位
                # 移动的位数由右操作数指定，右操作数必须是非负值，其右边空出的位用 0 填补，高位左移溢出则舍弃该高位
                # 这个操作就是不断的填充二进制
                num = 1 << i

                # 把二进制结果累加到 ans 上
                ans += num



        # 返回 ans 就行 
        # 在 Python 中需要对最高位进行特殊判断。
        return ans if cnt[31] % 3 == 0 else ~(ans ^ 0xffffffff)

四、动画理解（没有声音）

程序员吴师兄算法训练营永久会员

打赏 收藏 海报 链接