136. 只出现一次的数字
创始人
2025-06-01 20:01:40
0次
总结
异或位运算方法
给你一个非空整数 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例1：
输入：nums = [2,2,1]
输出：1
示例2:
输入：nums = [4,1,2,1,2]
输出：4
示例3:
输入：nums = [1]
输出：1
提示：
- 1 <= nums.length <= 3 * 104
- -3 * 104 <= nums[i] <= 3 * 104
- 除了某个元素只出现一次以外，其余每个元素均出现两次。
方法：位运算
思路与算法
异或运算有以下三个性质:
- 任何数和0做异或运算，结果仍然是原来的数，即a⊕0=aa⊕0=aa⊕0=a。
- 任何数和其自身做异或运算，结果是0，即a⊕a=0a⊕a=0a⊕a=0。
- 异或运算满足交换律和结合律，即a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=ba⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=ba⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
假设数组中有 2m+1 个数，其中有 m个数各出现两次，一个数出现一次。令a1、a2、……、ama_1、a_2、……、a_ma1、a2、……、am为出现两次的m个数，am+1a_{m+1}am+1为出现一次的数。根据性质3，数组中的全部元素的异或运算结果总是可以写成如下形式：
(a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕am+1(a_1⊕a_1)⊕(a_2⊕a_2)⊕⋯⊕(a_m⊕a_m)⊕a_{m+1} (a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕am+1
根据性质 2 和性质 1，上式可化简和计算得到如下结果：
0⊕0⊕⋯⊕0⊕am+1=am+10⊕0⊕⋯⊕0⊕a_{m+1}=a_{m+1} 0⊕0⊕⋯⊕0⊕am+1=am+1
因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
class Solution {
public:int singleNumber(vector& nums) {int ret=0;for (auto e: nums) ret ^= e;return ret;}
};
复杂度分析
- 时间复杂度：O(n)O(n)O(n)，其中n是数组长度。只需要对数组遍历一次。
- 空间复杂度：O(1)O(1)O(1)。
相关内容
热门资讯
港股稳定币概念暴涨！刘煜辉：人...
6月2日，在港股市场上，数字货币概念股集体拉升，连连数字盘中一度上涨80%，移卡一度涨近50%，欧科...
又现百万罚单 消金合作机构管理...
北京商报讯（记者 岳品瑜 董晗萱）消费金融机构的一张新罚单，又指向合作业务管理。6月2日，北京商报记...
国际金价重返高位 炒金是否卷土...
6月2日，国际金价重返3300美元/盎司高位，截至北京商报记者发稿，金价涨幅超过2%，盘中突破336...
股价翻倍基金霸屏 创新药否极泰...
证券时报记者 裴利瑞今年以来，中国创新药行业正经历了一场前所未有的价值重估，而且在近期呈现加速趋势。...
5000亿人民币新型融资政策工...
内容提要：中国计划推出5000亿元新型政策性金融工具，重点投向新基建与消费领域，以对冲出口压力。但企...
美国5月ISM制造业PMI连续...
6月2日周一，ISM公布的数据显示，美国5月ISM制造业活动连续三个月萎缩，在关税上调的背景下，进口...
国内油价或现年内第四涨 加满一...
中新经纬6月3日电 (万可义)国内成品油新一轮调价窗口将于6月3日24时开启。综合机构观点，国内...
道指三连阳！美股6月开门红，黄...
*三大股指上扬，纳指涨近0.7%；*中长期美债收益率走高，基准10年期美债报4.61%；*受特朗普言...
结构性行情或延续，券商建议6月...
经历5月冲高回落后，A股6月行情即将拉开帷幕。展望后市表现，当前机构多数持相对谨慎态度，认为市场短期...
马斯克卸任DOGE后旗下公司迎...
马斯克重返其商业帝国、远离政治后，其旗下公司迅速开启一系列融资，包括xAI正在启动一项3亿美元的股份...
媒体称美国秘密提案允许低浓缩铀...
媒体报道，美国对伊核谈判政策出现180度转变，美国政府上周六向伊朗提出一份新的核协议提案，其中允许伊...
一笔漂亮的退出：93亿卖始祖鸟...
(图片由豆包AI生成） 消费赛道又一明星公司被减持了。5月29日，据彭博社消息，始祖鸟母公司亚玛芬体...
速腾聚创一季度毛利同比增七成 ...
速腾聚创第二代灵巧手Papert 2.0。 5月30日，速腾聚创发布2025年第一季度财报。据...
“消费+科技”双轮驱动，港股市...
港股IPO市场正经历显著回暖，优质资产供给逐步改善，市场流动性增强，吸引了大量资金关注。Wind资讯...
从一面之恩到千亿帝国CEO，安...
近日，吉利汽车管理层大调整引发行业聚焦。在吉利一季度财报发布的当天，吉利控股集团宣布重大人事调整：极...
A股公司密集更名折射四大现象 ...
据不完全统计，2025年以来，超60家A股公司完成或启动名称变更工作，其中超30家公司涉及证券简称调...
券商6月“金股”出炉，两大行业...
A股6月开市在即，券商6月月度“金股”近期陆续出炉。Wind数据显示，截至6月2日中国证券报记者发稿...
朴朴永辉福州“停火” 永辉和朴...
交流朴朴永辉，实名添加微信lihua759321进群在福州前置仓生鲜到家市场，过往的两大主力玩家、总...
美股下跌，钢铁股大涨！金价重回...
6月2日，美国三大股指开盘走低，截至22:40发稿，道指跌0.5%，标普500指数跌0.25%，纳斯...
这个账单，决定后半辈子幸福… ...
图：Hiroki Kawanabe 第一波延迟退休的人出来了。 挺多人晒出来的退休年龄数字，已经有零...