购物网站设计模版,长沙seo网络优化,河南做网站企起,工业产品设计的基本特征【问题描述】[中等]
在一个数组 nums 中除一个数字只出现一次之外#xff0c;其他数字都出现了三次。请找出那个只出现一次的数字。示例 1#xff1a;输入#xff1a;nums [3,4,3,3]
输出#xff1a;4
示例 2#xff1a;输入#xff1a;nums [9,1,7,9,7,9,7]
输出其他数字都出现了三次。请找出那个只出现一次的数字。示例 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) {HashMapInteger,Integer map new HashMapInteger,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(int n : map.keySet()) {// if(map.get(n)1)// return n;// }for(Map.EntryInteger,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) {
MapString,String mapnew HashMapString,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 map1itmap.entrySet().iterator();while(map1it.hasNext()){Map.EntryString, String entry(EntryString, String) map1it.next();System.out.println(Key: entry.getKey() Value: entry.getValue());}//第三种推荐尤其是容量大时 System.out.println(\n通过Map.entrySet遍历key和value); for(Map.EntryString, 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/
