【问题描述】[中等]
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
【解答思路】
1. HashMap
时间复杂度：O(N) 空间复杂度：O(1)
public int singleNumber(int[] nums
) {
HashMap
<Integer,Integer> map
= new HashMap<Integer,Integer>();
for (int n
: nums
) {
if (map
.containsKey(n
)) {
map
.put(n
,map
.get(n
)+1);
} else {
map
.put(n
,1);
}
}
int i
= 0;
for(Map
.Entry
<Integer,Integer> d
:map
.entrySet()){
if(d
.getValue()==1)
return d
.getKey();
}
return -1;
}
二三解题思路
2. 有限状态自动机
时间复杂度：O(N) 空间复杂度：O(1)
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
;
}
}
3. 遍历统计
时间复杂度：O(N) 空间复杂度：O(1)
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
;
}
}
【总结】
1.遍历 HashMap 四种方法
public static void main(String
[] args
) {
Map
<String,String> map
=new HashMap<String,String>();
map
.put("1", "value1");
map
.put("2", "value2");
map
.put("3", "value3");
map
.put("4", "value4");
System
.out
.println("\n通过Map.keySet遍历key和value：");
for(String key
:map
.keySet())
{
System
.out
.println("Key: "+key
+" Value: "+map
.get(key
));
}
System
.out
.println("\n通过Map.entrySet使用iterator遍历key和value: ");
Iterator map1it
=map
.entrySet().iterator();
while(map1it
.hasNext())
{
Map
.Entry
<String, String> entry
=(Entry
<String, String>) map1it
.next();
System
.out
.println("Key: "+entry
.getKey()+" Value: "+entry
.getValue());
}
System
.out
.println("\n通过Map.entrySet遍历key和value");
for(Map
.Entry
<String, String> entry
: map
.entrySet())
{
System
.out
.println("Key: "+ entry
.getKey()+ " Value: "+entry
.getValue());
}
System
.out
.println("\n通过Map.values()遍历所有的value，但不能遍历key");
for(String v
:map
.values())
{
System
.out
.println("The value is "+v
);
}
}
2.状态机 数电 设计逻辑电路的状态转换图
3.个人认为掌握方法一 HashMap和 方法三 统计遍历 足够了 ，有数电或对状态机感兴趣的可以使用方法二
位运算 判相等异或^ 取位与&1 置位或|1
转载链接：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/
