Day22_数组中的重复数字_剑指Offer
IT蛋
2023-04-13 11:35
阅读2574
数组中数字出现的次数
medium 原题连接：数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
- 2 <= nums.length <= 10000
解题思路
因为题目要求了时间复杂度不能超过O(n)，空间复杂度不能超过O(1)，所以无法使用HashMap做记录统计值
前置知识：
- 关于异或（相同返回0，不同返回1）：A^A=0 , A^B=B^A 和 A^0=A ，所以A^B^A = A^A^B = 0^B = B
- 一个十位数，对应着唯一的二进制值（废话），所以如果两个数的二进制某个位置值不同，那一定是不同值
实现：
- 对nums中所有数据进行异或，能得到除了重复数字之外的，两个只出现了一次的数的异或结果
- 找到这个异或结果的一个“1”，因为是不同值，所以异或一定不为0，找到一个异或结果为1的部分，说明两个数在这个位置二进制值一定不同
- 根据2得到的部位，将nums划分为两个部分分别进行异或，得到的两个值就是目标
Java代码
class Solution {
public int[] singleNumbers(int[] nums) {
int ans1 = 0, ans2 = 0, mid = 0, firstDif = 1;
// 1.找出两个单次出现的数字的异或结果
for(int num : nums) {
mid = mid ^ num;
}
// 2.找到区分位
while((mid & firstDif) == 0) {
firstDif = firstDif << 1;
}
// 3.依据区分为去异或
for(int num : nums) {
if((num & firstDif) == 0)ans1 = ans1 ^ num;
else ans2 = ans2 ^ num;
}
return new int[]{ans1, ans2};
}
}
数组中数字出现的次数 II
medium 原题连接：数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例：
输入：nums = [3,4,3,3]
输出：4
输入：nums = [9,1,7,9,7,9,7]
输出：1
提示：
- 1 <= nums.length <= 10000
- 1 <= nums[i] < 2^31
解题思路
- 数组中出现三次，说明数字转换成二进制后，每个为1的对应位置在数组中会至少有3个1
- 将nums的数字全部转换为32位二进制，按对应位填入32位的数组
- 对该数组每一位都对3取余，只出现一次的会留下一个1
- 重新拼接数组为十进制数，得到结果
Java代码
class Solution {
public int singleNumber(int[] nums) {
// 1.遍历数组，每一位都拆为二进制，按值放入32位数组
int[] ans = new int[32];
for(int num : nums) {
int i=0;
while(num >0 ) {
ans[i] += num%2;
num /= 2;
i++;
}
}
// 2.对数组每一位都取3的模，获得结果
for(int i=0; i < ans.length; i++) {
ans[i] = ans[i]%3;
}
// 3.将结果拼为十位数
int value = 0;
for(int i=ans.length-1; i>=0; i--) {
value *= 2;
value += ans[i];
}
return value;
}
}
设计项目总是会在前端上掉链子，掉头发的嘞...
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
内容推荐
刷题经验分享
60
Leetcode文章资源分享：高效刷满500题方法论
170
这几天刷题算法，我也是入门基础，虽然还是难，思路啥的，但是温习了很多，比如map集合的containsKey等等 set的去重 map的计数等等今天刷了一道算法中等二维数组的 零矩阵 虽然还是查阅了资料但是没看题解，就是二维数组的列长度计算。。跌跌撞撞终于写出了一道中等题目[流泪][流泪]，，很开心。想放弃的，但是写出来那种成就感很足，继续加油吧[呲牙]
10
才发现力扣评论区也显示ip属地了，是从今天还是昨天开始的，刚注意到[捂脸]
15
学习总结 Python 算法 前端关于过去一年的学习情况去年尝试学习了MCU学了有一周左右弃了，然后抄网上的flask框架的项目，搞到一半发现有一些前端的问题不怎么明白，然后开始刷前端当前学到BOM，然后是算法刷了100多道 目前除了动态规划不怎么行 其他题目看到都还有点思路
8
