死磕算法系列文章
“Leetcode :
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_40_singleNumbers_2/Solution.java
“题目描述 :一个整型数组
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]
异或运算有个重要的性质,两个相同数字异或为 0。因此,若将 nums 中所有数字执行异或运算,留下的结果则为 出现一次的数字 x ,即:
设 nums = [3, 3, 4, 4, 1],以上计算流程如下图所示。
算法流程:
复杂度分析:
package com.nateshao.sword_offer.topic_40_singleNumbers;
/**
* @date Created by 邵桐杰 on 2022/1/18 21:33
* @微信公众号 千羽的编程时光
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description:
*/
public class Solution {
public static void main(String[] args) {
int[] arr = {4, 1, 4, 6};
System.out.println("singleNumbers(arr) = " + singleNumbers(arr));
}
public static 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. 返回出现一次的数字
}
}
“题目描述 :在一个数组
nums
中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。 难度:中等
示例 1:
输入:nums = [3,4,3,3]
输出:4
示例 2:
输入:nums = [9,1,7,9,7,9,7]
输出:1
使用HashMap的原理是统计每个数字出现的次数,因为只有一个数字出现一次,其他都出现3次
,我们只需要返回那个出现一次的即可,原理比较简单,我们来看下代码
package com.nateshao.sword_offer.topic_40_singleNumbers_2;
import java.util.HashMap;
import java.util.Map;
/**
* @date Created by 邵桐杰 on 2022/1/18 21:33
* @微信公众号 千羽的编程时光
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description:
*/
public class Solution {
public static void main(String[] args) {
int[] arr = {9, 1, 7, 9, 7, 9, 7};
int[] arr2 = {3,4,3,3};
System.out.println("singleNumber(arr) = " + singleNumber(arr));
System.out.println("singleNumber(arr2) = " + singleNumber(arr2));
}
public static int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
//先把数字存储到map中,其中key存储的是当前数字,value是
//数字的出现的次数
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
//最后在遍历map中的所有元素,返回value值等于1的
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1)
return entry.getKey();
}
return -1;
}
}
参考链接: