LeetCode每日一题题解:剑指 Offer II 004. 只出现一次的数字 -题解-python && C++源代码

简介: LeetCode每日一题题解:剑指 Offer II 004. 只出现一次的数字 -题解-python && C++源代码

剑指 Offer II 004. 只出现一次的数字


难度中等52收藏分享切换为英文接收动态反馈


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


示例 1:


输入:nums = [2,2,3,2]

输出:3

示例 2:


输入:nums = [0,1,0,1,0,1,100]

输出:100

提示:


1 <= nums.length <= 3 * 104

-231 <= nums[i] <= 231 - 1

nums 中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次

题目思路:


这道题的思路总的来说很简答,就是将每个数变成二进制的,这么来说,数组中的所有数都变成二进制的参与本程序的运算,

对于每个数来说,不管是什么数当他变成二进制之后他的每一位不是0就是1,我们对数组中每个数变成二进制之后的每一位

进行求和,然后对3进行取余,就会得到单独出现的那位数,(因为其他的数都是出现三次的,所有对3取余之后都为0,多出来

的那个就是只出现一次的),如果这个数位1,则将1移动到i位置上,与a进行或运算,相当于在i位上赋1,如果是0则不用管

因为在移动过程中会对没有运算的地方自动补0.


python代码:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0  #构建变量a = 0
        for i in range(32):  #遍历32位数,因为所有数转换为二进制的话,一共可有32位
            total = sum((num >> i) & 1 for num in nums)   #定义个整数来存储数组的某位的数相加的和,所有数的某位数相加 得到all
            if total % 3:  #如果all%3 为0,则不进行如下操作,直接跳入下一个循环,因为当前补0即可
                if i == 31:  #/如果all%3 为0,则不进行如下操作,直接跳入下一个循环,因为当前补0即可
                    ans = ans - (1 << i)  #因为python对有符号数和无符号数没有区分,因此我们这里需要进行31位的判断
                else:
                    ans = ans | (1 << i)  #如果为1的话,则需要将1位移到相应的位置,然后与a进行或运算,即在a的i位上赋值1
        return ans

C++代码:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0;  //构建变量a = 0
        for (int i = 0; i < 32; i++){  //遍历32位数,因为所有数转换为二进制的话,一共可有32位
            int all = 0;    //定义个整数来存储数组的某位的数相加的和
            for (int num: nums){
                all += (num>>i)&1;  //所有数的某位数相加 得到all
            }
            if (all%3){    //如果all%3 为0,则不进行如下操作,直接跳入下一个循环,因为当前补0即可
                a |= 1<<i;    //如果为1的话,则需要将1位移到相应的位置,然后与a进行或运算,即在a的i位上赋值1
            }
        }
        return a;  //输出答案
    }
};
相关文章
|
1月前
|
Go C++
【力扣】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
【2月更文挑战第18天】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)
34 6
|
1月前
|
C++
两种解法解决 LeetCode 27. 移除元素【C++】
两种解法解决 LeetCode 27. 移除元素【C++】
|
2月前
|
C++ 计算机视觉 Python
我在Python中丢的面子被我用C++找回来了
我在Python中丢的面子被我用C++找回来了
29 0
|
9天前
|
算法 Java C语言
C++和Java中的随机函数你玩明白了吗?内附LeetCode470.rand7()爆改rand10()巨详细题解,带你打败LeetCode%99选手
C++和Java中的随机函数你玩明白了吗?内附LeetCode470.rand7()爆改rand10()巨详细题解,带你打败LeetCode%99选手
|
13天前
|
人工智能 机器人 C++
【C++/Python】Windows用Swig实现C++调用Python(史上最简单详细,80岁看了都会操作)
【C++/Python】Windows用Swig实现C++调用Python(史上最简单详细,80岁看了都会操作)
|
30天前
|
编译器 测试技术 C++
【Python 基础教程 01 全面介绍】 Python编程基础全攻略:一文掌握Python语法精髓,从C/C++ 角度学习Python的差异
【Python 基础教程 01 全面介绍】 Python编程基础全攻略:一文掌握Python语法精髓,从C/C++ 角度学习Python的差异
159 0
存储 编译器 Linux
18 0
|
18天前
|
C++ Python
【C++/Python】C++调用python文件
【C++/Python】C++调用python文件
|
1月前
|
Go C++
【力扣】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
【2月更文挑战第17天】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)
31 8
|
2月前
|
存储 Java Go
对比 C++ 和 Python,谈谈指针与引用
对比 C++ 和 Python,谈谈指针与引用
55 1