【查找算法】找到数组中只出现1次的数字(附Python实现代码)

简介: 找到数组中只出现1次的数字(附Python实现代码)

问题

给定一个整型数组nums,除某个元素仅出现1次,其余元素都出现3次,找出并返回只出现了1次的元素。

约束条件
1 <= nums.length <= 3 10 * 4
-2 * 31 <= nums[i] <= 2 * 31 - 1 (
表示幂)

示例一:
输入:nums = [2,2,2,3]
输出:3
示例二:
输入:nums = [4,4,6,6,4,5,6]
输出:5
AI 代码解读

解题思路

整体思路: 通过与数组中元素的二进制位一位一位的比较,找到某一位有且唯一不同的元素。

这道题涉及到位运算,通过与运算&,移位<<,一起异或^找到指定元素,可以先了解位运算相关基础知识。

  • 通过bit = 1 << i结合i循环实现,<<是左移位,bit用来与数组元素进行比较。
  • 进入第i次循环,bit的第i位是1,其余都是0,此时循环数组中的元素,如果数组元素与bit的第i位相同,count计数加一,数组循环结束后:
    -- 如果count % 3 ==0,说明该位相同的数是3的整数倍个,因此要找的元素这一位不是1
    -- 如果count % 3 ==1,说明该位相同的数不是3的整数倍个,因此要找的元素这一位是1
  • 确定该元素的第i位是0或1之后,bit就要移位进行下一次的比较了,因此我们要把刚才的结果存起来,这时候就要用到异或^,设置一个二进制位全为0的临时变量tmp,0和0异或为0、0个1异或为1,这样就能存下来了。
  • exp:[1,1,1,0,0,0,3,3,3,4]
    -- 比较数组元素二进制第0位,有6个是1,4个是0,count = 6说明单独的这个数第0位不是1而是0,tmp不需要变化;
    -- 再比较第1位,有3个是1,7个是0,count = 3说明单独的这个数第1位不是1而是0,tmp不需要变化;
    -- 再比较第2位,有1个是1,9个是0,count = 1说明单独的这个数第2位是1,tmp与此时的bit异或。
    -- ...一直比较到第31位
    最后我们得到的tmp就是那个单独存在的元素。

代码实现

class Solution(object):
    def findNumber(self, nums):
        tmp = 0
        for i in range(32):
            count = 0
            bit = 1 << i # 1,10,100,1000...
            print(f'bit:{bin(bit)}')
            for num in nums:
                print(f'num:{bin(num)}')
                if num & bit:
                    count += 1
            print(f'count:{count}')
            if count %3 != 0:
                tmp ^= bit
                print(f'tmp:{bin(tmp)}')
        return tmp

s = Solution()
nums = [1,2,1,2,1,4,2]
ans = s.findNumber(nums)
print(ans)
AI 代码解读
目录
打赏
0
0
0
0
16
分享
相关文章
从零复现Google Veo 3:从数据预处理到视频生成的完整Python代码实现指南
本文详细介绍了一个简化版 Veo 3 文本到视频生成模型的构建过程。首先进行了数据预处理,涵盖了去重、不安全内容过滤、质量合规性检查以及数据标注等环节。
116 5
从零复现Google Veo 3:从数据预处理到视频生成的完整Python代码实现指南
从零开始200行python代码实现LLM
本文从零开始用Python实现了一个极简但完整的大语言模型,帮助读者理解LLM的工作原理。首先通过传统方法构建了一个诗词生成器,利用字符间的概率关系递归生成文本。接着引入PyTorch框架,逐步重构代码,实现了一个真正的Bigram模型。文中详细解释了词汇表(tokenizer)、张量(Tensor)、反向传播、梯度下降等关键概念,并展示了如何用Embedding层和线性层搭建模型。最终实现了babyGPT_v1.py,一个能生成类似诗词的简单语言模型。下一篇文章将在此基础上实现自注意力机制和完整的GPT模型。
143 14
从零开始200行python代码实现LLM
200行python代码实现从Bigram模型到LLM
本文从零基础出发,逐步实现了一个类似GPT的Transformer模型。首先通过Bigram模型生成诗词,接着加入Positional Encoding实现位置信息编码,再引入Single Head Self-Attention机制计算token间的关系,并扩展到Multi-Head Self-Attention以增强表现力。随后添加FeedForward、Block结构、残差连接(Residual Connection)、投影(Projection)、层归一化(Layer Normalization)及Dropout等组件,最终调整超参数完成一个6层、6头、384维度的“0.0155B”模型
126 11
200行python代码实现从Bigram模型到LLM
把Postman调试脚本秒变Python采集代码的三大技巧
本文介绍了如何借助 Postman 调试工具快速生成 Python 爬虫代码,并结合爬虫代理实现高效数据采集。文章通过“跨界混搭”结构,先讲解 Postman 的 API 调试功能,再映射到 Python 爬虫技术,重点分享三大技巧:利用 Postman 生成请求骨架、通过 Session 管理 Cookie 和 User-Agent,以及集成代理 IP 提升稳定性。以票务信息采集为例,展示完整实现流程,探讨其在抗封锁、团队协作等方面的价值,帮助开发者快速构建生产级爬虫代码。
106 1
把Postman调试脚本秒变Python采集代码的三大技巧
图神经网络在信息检索重排序中的应用:原理、架构与Python代码解析
本文探讨了基于图的重排序方法在信息检索领域的应用与前景。传统两阶段检索架构中,初始检索速度快但结果可能含噪声,重排序阶段通过强大语言模型提升精度,但仍面临复杂需求挑战
89 0
图神经网络在信息检索重排序中的应用:原理、架构与Python代码解析
多模态RAG实战指南:完整Python代码实现AI同时理解图片、表格和文本
本文探讨了多模态RAG系统的最优实现方案,通过模态特定处理与后期融合技术,在性能、准确性和复杂度间达成平衡。系统包含文档分割、内容提取、HTML转换、语义分块及向量化存储五大模块,有效保留结构和关系信息。相比传统方法,该方案显著提升了复杂查询的检索精度(+23%),并支持灵活升级。文章还介绍了查询处理机制与优势对比,为构建高效多模态RAG系统提供了实践指导。
472 0
多模态RAG实战指南:完整Python代码实现AI同时理解图片、表格和文本
Python与MongoDB的亲密接触:从入门到实战的代码指南
本文详细介绍了Python与MongoDB结合使用的实战技巧,涵盖环境搭建、连接管理、CRUD操作、高级查询、索引优化、事务处理及性能调优等内容。通过15个代码片段,从基础到进阶逐步解析,帮助开发者掌握这对黄金组合的核心技能。内容包括文档结构设计、批量操作优化、聚合管道应用等实用场景,适合希望高效处理非结构化数据的开发者学习参考。
67 0
|
2月前
|
Apriori算法的Python实例演示
经过运行,你会看到一些集合出现,每个集合的支持度也会给出。这些集合就是你想要的,经常一起被购买的商品组合。不要忘记,`min_support`参数将决定频繁项集的数量和大小,你可以根据自己的需要进行更改。
118 18
论上网限制软件中 Python 动态衰减权重算法于行为管控领域的创新性应用
在网络安全与行为管理的学术语境中,上网限制软件面临着精准识别并管控用户不合规网络请求的复杂任务。传统的基于静态规则库或固定阈值的策略,在实践中暴露出较高的误判率与较差的动态适应性。本研究引入一种基于 “动态衰减权重算法” 的优化策略,融合时间序列分析与权重衰减机制,旨在显著提升上网限制软件的实时决策效能。
72 2

热门文章

最新文章

推荐镜像

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等