目录
-
- 题目：
-
-
- [剑指 Offer 56 - I. 数组中数字出现的次数](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/)
- 题目分析
-
- 初始解答：
- 学习他人：
-
- 方法一:
- 方法二：
- 方法三：
- 位运算
- 题目：
-
-
- [剑指 Offer 56 - II. 数组中数字出现的次数 II](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/)
- 题目分析
-
- 初始解答：
- 学习他人：
-
- 方法一:
- 方法二：
- 方法三：
- 方法四：
-
- 方法一：有限状态自动机
- 方法二：遍历统计
- 总结
刷题日期：下午7:15 2021年5月19日星期三
个人刷题记录，代码收集，来源皆为leetcode
经过多方讨论和请教，现在打算往Java方向发力
主要答题语言为Java
题目：
剑指 Offer 56 - I. 数组中数字出现的次数
难度中等389
一个整型数组
nums
里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
题目分析
根据时间复杂度，可以遍历一次，根据空间复杂度，需要原地或者只开辟一个长度为2的数组存放结果。
应该有两种方式，一种是把数组排序，然后取出某两个和前后都不相等的元素。
一种是遍历一遍数组，然后不断地把元素填入，取出结果数组。
初始解答：
先尝试第二种方法：
class Solution {
public int[] singleNumbers(int[] nums) {
if(nums.length == 2) return nums; //边界条件
int[] res = new int[2];
int index = 0; //结果数组下标
res[0] = nums[0], res[1] = nums[1];
for(int i = 2; i < nums.length; i++) {
//难点在于到底替换第一个还是第二个元素
if(res[0] == nums[i] && res[1] != nums[i]) {
res[0] = 0;
}
//根据第二个示例，两个元素地数组也根本不够，必须先弄个链表或者队列，再把最后剩下的两个转成数组返回
}
}
感觉自己想的还是太简单了。
尝试第一种方法：
class Solution {
public int[] singleNumbers(int[] nums) {
Arrays.sort(nums);
if(nums.length == 2) return nums; //边界条件
int[] res = new int[2];
res[0] = 0;
res[1] = 0;
int index = 0; //结果数组下标
for(int i = 0; i < nums.length; i++) {
if(i == 0 && nums[i] != nums[i + 1]) res[index++] = nums[i];
if(i == (nums.length - 1) && nums[i - 1] != nums[i]) res[index++] = nums[i];
if( i > 0 && i < (nums.length - 1) && nums[i - 1] != nums[i] && nums[i] != nums[i + 1]) res[index++] = nums[i];
}
return res;
}
}
效率有点低，但是总算是通过了，边缘条件其实蛮多的，还要考虑非重复元素在头尾的情况。
执行结果：通过
显示详情 添加备注
执行用时：10 ms, 在所有 Java 提交中击败了15.68%的用户
内存消耗：40.3 MB, 在所有 Java 提交中击败了19.75%的用户
看了评论，都是异或解算出来的，学习K神
class Solution {
public int[] singleNumbers(int[] nums) {
int x = 0, y = 0, n = 0, m = 1;
for(int num : nums) {
n ^= num; //遍历异或
}
while((n & m) == 0) {
m <<= 1; //循环左移计算m
}
for(int num : nums) { //遍历nums分组
if((num & m) != 0) {
x ^= num;
} else{
y ^= num;
}
}
return new int[] {x, y}; //出现一次的数字
}
}
执行结果： 通过
显示详情 添加备注
执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.2 MB, 在所有 Java 提交中击败了43.18%的用户
具体不深究了，需要时再好好分析。
学习他人：
方法一:
扭秧歌的一只泱L3
2020-03-31
这道题充分运用了异或运算的各种性质 并且学习了提交记录中排第一的优化方案
首先要知道异或运算的几个性质
- 交换律
- 结合律（即(ab)c == a(bc)）
- 对于任何数x，都有xx=0，x0=x
- 自反性 A XOR B XOR B = A xor 0 = A —> A XOR B = C 则 C XOR B = A
以上性质摘自异或的性质及运用
具体思路其他题解都说的很明白了，这里就直接结合代码在注释中说明几种性质的运用。
代码
class Solution {
// 假设结果数为A B
public int[] singleNumbers(int[] nums) {
int x = 0; // 用于记录 A B 的异或结果
/** 得到A^B的结果
基于异或运算的以下几个性质
1. 交换律
2. 结合律
3. 对于任何数x，都有x^x=0，x^0=x
*/
for (int val : nums) x ^= val;
// x & (-x)本身的作用是得到最低位的1，
int flag = x & (-x);
// 而我们所需要的做到的是：利用这个1来进行分组，也就是做到将A和B区分开
// 前面已经知道，x是我们需要的结果数A和B相异或的结果，也就是说，x的二进制串上的任何一个1，都能成为区分A和B的条件
// 因此我们只需要得到x上的任意一个1，就可以做到将A和B区分开来
int res = 0; // 用于记录A或B其中一者
// 分组操作
for (int val : nums) {
// 根据二进制位上的那个“1”进行分组
// 需要注意的是，分组的结果必然是相同的数在相同的组，且还有一个结果数
// 因此每组的数再与res=0一路异或下去，最终会得到那个结果数A或B
// 且由于异或运算具有自反性，因此只需得到其中一个数即可
if ((flag & val) != 0) {
res ^= val;
}
}
// 利用先前的x进行异或运算得到另一个，即利用自反性
return new int[] {res, x ^ res};
}
}
方法二：
JuneHuaL2
2020-02-25
nums = [1,2,10,4,1,4,3,3]
- a^a=0
- a^0=a
- abc=acb
- a&(-a)=最低位为1的二进制（从又到左）
- 所有的异或结果得到sum=2^10=8
- flag=-8&8=8
- 可分为两组，一组为与flag相与等于1的[10]，另一组为0的[1,2,4,1,4,3,3]
- 组内异或分别得到【10】【2】
class Solution {
public int[] singleNumbers(int[] nums) {
int sum=0;
//得到异或结果，即为不相同两个数的异或结果sum
for(int num:nums)
sum^=num;
//得到sum的二进制的1的最低位
int flag=(-sum)∑
int result[]=new int[2];
//分成两个组进行异或，每组异或后的结果就是不相同两个数的其中之一
for(int num:nums){
if((flag&num)==0)
result[0]^=num;
else{
result[1]^=num;
}
}
return result;
}
}
方法三：
K神，分析的透
题目要求时间复杂度 O(N)，空间复杂度 O(1)，因此首先排除 暴力法 和 哈希表统计法 。
简化问题： 一个整型数组 nums 里除 一个 数字之外，其他数字都出现了两次。
作者：jyd
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom/
来源：力扣（LeetCode）
本题难点： 数组 numsnum**s 有 两个 只出现一次的数字，因此无法通过异或直接得到这两个数字。
class Solution {
public int[] singleNumbers(int[] nums) {
int x = 0, y = 0, n = 0, m = 1;
for(int num : nums) // 1. 遍历异或
n ^= num;
while((n & m) == 0) // 2. 循环左移，计算 m
m <<= 1;
for(int num: nums) { // 3. 遍历 nums 分组
if((num & m) != 0) x ^= num; // 4. 当 num & m != 0
else y ^= num; // 4. 当 num & m == 0
}
return new int[] {x, y}; // 5. 返回出现一次的数字
}
}
那我总不能天天CV吧 2021-04-13
自己拿例子走了一遍流程才慢慢清晰起来，希望能帮助到更多跟我一样笨蛋的小伙伴吧呜呜呜呜呜
class Solution {
public int[] singleNumbers(int[] nums) {
//因为相同的数字异或为0，任何数字与0异或结果是其本身。
//所以遍历异或整个数组最后得到的结果就是两个只出现一次的数字异或的结果：即 z = x ^ y
int z = 0;
for(int i : nums) z ^= i;
//我们根据异或的性质可以知道：z中至少有一位是1，否则x与y就是相等的。
//我们通过一个辅助变量m来保存z中哪一位为1.（可能有多个位都为1，我们找到最低位的1即可）。
//举个例子：z = 10 ^ 2 = 1010 ^ 0010 = 1000,第四位为1.
//我们将m初始化为1，如果（z & m）的结果等于0说明z的最低为是0
//我们每次将m左移一位然后跟z做与操作，直到结果不为0.
//此时m应该等于1000，同z一样，第四位为1.
int m = 1;
while((z & m) == 0) m <<= 1;
//我们遍历数组，将每个数跟m进行与操作，结果为0的作为一组，结果不为0的作为一组
//例如对于数组：[1,2,10,4,1,4,3,3]，我们把每个数字跟1000做与操作，可以分为下面两组：
//nums1存放结果为0的: [1, 2, 4, 1, 4, 3, 3]
//nums2存放结果不为0的: [10] (碰巧nums2中只有一个10，如果原数组中的数字再大一些就不会这样了)
//此时我们发现问题已经退化为数组中有一个数字只出现了一次
//分别对nums1和nums2遍历异或就能得到我们预期的x和y
int x = 0, y = 0;
for(int i : nums) {
//这里我们是通过if...else将nums分为了两组，一边遍历一遍异或。
//跟我们创建俩数组nums1和nums2原理是一样的。
if((i & m) == 0) x ^= i;
else y ^= i;
}
return new int[]{x, y};
}
}
位运算
木木
（编辑过）2020-04-28
知识储备 位运算：
&（与）：真真为真，一假为假（一为0，则为0）（例如： 0011&0101 = 0001）
| （或）：一真为真，假假为假（一为1，则为1）（例如： 0011|0101 =0111）
~（非）：真为假，假为真（~0011 = 1100）
^（异或）：不同为真，相同为假（例如： 0011|0101 =1001）
<<（左移）：二进制向左移动一位，末尾补0
>>（右移）： 二进制向右移动一位 101101 >>1 101101->10110
题目：
剑指 Offer 56 - II. 数组中数字出现的次数 II
难度中等182
在一个数组
nums
中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
题目分析
两次变三次
初始解答：
笨办法的话好像都不用怎么改
class Solution {
public int singleNumber(int[] nums) {
Arrays.sort(nums);
if(nums.length == 1) return nums[0]; //边界条件
int index = 0; //结果数组下标
for(int i = 0; i < nums.length; i++) {
if(i == 0 && nums[i] != nums[i + 1]) index = nums[i];
if(i == (nums.length - 1) && nums[i - 1] != nums[i]) index = nums[i];
if( i > 0 && i < (nums.length - 1) && nums[i - 1] != nums[i] && nums[i] != nums[i + 1]) index = nums[i];
}
return index;
}
}
执行结果：通过
显示详情 添加备注
执行用时：9 ms, 在所有 Java 提交中击败了54.69%的用户
内存消耗：39.2 MB, 在所有 Java 提交中击败了84.10%的用户
希望的解法肯定还是骚操作，竟然是位运算，真的了
学习方法一比较规矩的解法：
class Solution {
public int singleNumber(int[] nums) {
int[] help = new int[32];
for(int num : nums) {
for(int i = 0; i < 32; i++) {
help[i] += (num & (1 << i)) != 0 ? 1 : 0; //lambda表达式
}
}
int res = 0;
for(int i = 0; i < 32; i++) {
res += (1 << i) * (help[i] % 3);
}
return res;
}
}
执行结果：通过
显示详情 添加备注
执行用时：17 ms, 在所有 Java 提交中击败了20.49%的用户
内存消耗：39.3 MB, 在所有 Java 提交中击败了72.07%的用户
学习他人：
方法一:
cool 2020-04-30 按照剑指Offer书上的提示写出来的·～
class Solution {
public int singleNumber(int[] nums) {
int[] help = new int[32];
for(int num:nums){
for(int i = 0;i<32;i++){
help[i] += (num&(1<<i)) != 0 ? 1 : 0;
}
}
int res = 0;
for(int i = 0;i<32;i++){
res += (1<<i) * (help[i] % 3);
}
return res;
}
}
方法二：
mdlrL1 （编辑过）2021-05-09
数电只能理解到这里了
class Solution {
public int singleNumber(int[] nums) {
// 可以设计一种逻辑，使数字出现 3 次时，该逻辑的结果为 0（即只有 0，1，2 三种状态）
// 其实就是一个 三进制
// 一位二进制数只能存储 0 和 1 两种状态，所以我们需要用到两位二进制
// 设两位二进制数的高位为 A，低位为 B。C 是输入变量
// 表示的三种情况为 ： 0次：00(A=0,B=0), 1次：01(A=0,B=1), 2次：10(A=1,B=0)
// 注：11(A=1,B=1) 为无效输入
// 画出关于 A 的卡诺图（AB为11的结果是不重要的，用 x 表示）：
// AB\C | 0 | 1
// =================
// 00 | 0 | 0
// 01 | 0 | 1 ====> 得到 A = BC + AC'
// 11 | x | x
// 10 | 1 | 0
// 画出关于 B 的卡诺图
// AB\C | 0 | 1
// =================
// 00 | 0 | 1
// 01 | 1 | 0 ====> 得到 B = BC' + A'B'C
// 11 | x | x
// 10 | 0 | 0
// 很明显啊，我们需要的就是只出现一次的情况 01（A=0，B=1），即 B 的结果
int A = 0, B = 0;
for (int C : nums) {
int tmp = A;
A = (B & C) | (A & ~C);
B = (B & ~C) | (~tmp & ~B & C);
}
return B;
}
}
方法三：
屁屁L1 2020-03-31
菜鸡我只会map啊 感觉没学到东西
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap();
for (int i = 0; i < nums.length; i++) {
int a = map.getOrDefault(nums[i], 0);
map.put(nums[i], a + 1);
}
for (Integer a : map.keySet()) {
if(map.get(a) == 1) return a;
}
return -1;
}
}
方法四：
K神
如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。
作者：jyd
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/
来源：力扣（LeetCode）
方法一：有限状态自动机
各二进制位的 位运算规则相同 ，因此只需考虑一位即可。如下图所示，对于所有数字中的某二进制位 1 的个数，存在 3 种状态，即对 3 余数为 0, 1, 2。
class Solution {
public int singleNumber(int[] nums) {
int ones = 0, twos = 0;
for(int num : nums){
ones = ones ^ num & ~twos;
twos = twos ^ num & ~ones;
}
return ones;
}
}
方法二：遍历统计
此方法相对容易理解，但效率较低，总体推荐方法一。
class Solution {
public int singleNumber(int[] nums) {
int[] counts = new int[32];
for(int num : nums) {
for(int j = 0; j < 32; j++) {
counts[j] += num & 1;
num >>>= 1;
}
}
int res = 0, m = 3;
for(int i = 0; i < 32; i++) {
res <<= 1;
res |= counts[31 - i] % m;
}
return res;
}
}
总结
以上就是本题的内容和学习过程了，又是异或又是位运算的，到时候再专门复习吧，就算面试遇到了，都考这种了也不挣扎了，大家加油。
欢迎讨论，共同进步。