【問題描述】[中等]

在一個數組 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(int n : map.keySet()) {// if(map.get(n)==1)// return n;// }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/

總結

以上是生活随笔為你收集整理的[剑指offer]面试题第[56-2]题[JAVA][数组中数字出现的次数][状态机][hashmap][位运算]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。