type
status
date
slug
summary
tags
category
icon
password
创建时间
Nov 1, 2024 11:49 AM
一、136. 只出现一次的数字
给你一个 非空 整数数组
nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。针对这个问题，我们可以使用异或位运算来解决。异或位运算是，相同为 0，不同为 1。因此，出现两次的数字，会都变为 0，留下来的就是出现一次数字的。
二、137. 只出现一次的数字 II
给你一个整数数组
nums ，除某个元素仅出现 一次外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。追问: 一个数组，其中一个数字出现一次，其余出现 K 次(K为大于 1 的奇数)，找出只出现一次的数字。──如上
三、260. 只出现一次的数字 III
给你一个整数数组
nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。这个需要遍历两次，第一次得到的数字，是两个只出现一次元素的异或值。我们可以找到这个数字第一个 1 出现的位置，也就是两个只出现一次元素第一次出现不同的位置。我们以这个为判断点，可以把数组分为两组，这两个数字就会被分开。
注意：需要防止溢出
位运算扩展
异或：相同为 0，不同为 1。也可用「不进位加法」 来理解。
异或操作的一些特点：
实战常用的位运算操作
更为复杂的位运算操作
- 将x最右边的n位清零：
x & ( ~0 << n )
- 获取x的第n位值（0 或者 1）：
( x >> n ) & 1
- 获取x的第n 位的幂值：
x & ( 1 << ( n - 1 ))
- 仅将第n位置为1：
x | ( 1 << n)
- 仅将第n位置为0：
x & ( ~( 1 << n ))
- 将x最高位至第n位（含）清零：
x & (( 1 << n) - 1 )
- 将第n位至第0位（含）清零：
x & ( ~(( 1 << ( n + 1)) - 1))