天天演算法 | Easy | 13. Single number : 出現一次的數字

每天來一道，面試不卡殼，今天是天天演算法陪你成長的第13天

本題目可在 LeetCode 上 OJ， 鏈接為 Single Number

本篇解析採用了三種不同的思路~

題目描述：

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

題目翻譯

給出一組整數數組，除了一個元素只出現一次外，其餘都出現了兩次。找出那個只出現一次的。

注意： 你的演算法的時間複雜度應該是線性的。你可以不使用額外的存儲空間來完成它嗎？

解題方案

標籤： Hash Table、Bit Manipulation

思路：

方法一：Hash Table（HashMap-Java）

• 遍曆數組，將數組中的元素放入HashMap，無該值則放入，有該值則刪除
• 如此，最後只剩下一個鍵值對，其中的key值就是所求

方法二：Bit Manipulation ：

• 將一個數字和0異或，會得到該數字本身

a ⊕ 0 = an

• 兩個相同的數字異或，會得到0

a ⊕ a = 0n

• 並且有

a ⊕ b ⊕ a = ( a ⊕ a ) ⊕ b = 0 ⊕ b = bn

• 因此，我們可以將所有元素異或來獲得特別的那一個
• 時間複雜度： O(n)
• 空間複雜度： O(1)

方法三：Math ：

• 使用數學方法，如雞兔同籠問題的解法。
• 因為只有一個數出現了一次，所以用HashSet獲取「頭」的數目，出現了兩次所以乘以2
• 然後減去遍曆數組獲取的「腳」的數目，即得到只出現了一次的元素。
• 時間複雜度: O(n+n)=O(n)
• 空間複雜度: O(n+n)=O(n)

（ a + b + c ) * 2 - ( a + a + b + b + c ) = cn

代碼：

//方法一：Hash Table（HashMap）nclass Solution {n public int singleNumber(int[] nums) {n if(nums.length==0||nums==null){n return 0;n }n HashMap<Integer , Integer> map = new HashMap<Integer , Integer>();n for(int i=0;i<nums.length;i++){n if(!map.containsKey(nums[i])){n map.put(nums[i],1);n }n else{n map.remove(nums[i]);n }n }n for(Map.Entry<Integer, Integer> m : map.entrySet()){n return m.getKey();n }n return 0;n }n}nn//方法二：Bit Manipulationnclass Solution {n public int singleNumber(int[] nums) {n int res = 0;n for(int i = 0; i < nums.length; i++){n res = res ^ nums[i];n }n return res;n }n}nn//方法三：Mathnclass Solution {n public int singleNumber(int[] nums) {n if(nums.length==0||nums==null){n return 0;n }n int sum=0;n Set<Integer> set= (Set<Integer>) new HashSet();n for(int i=0;i<nums.length;i++){n set.add(nums[i]);n sum+=nums[i];n }n int sum2=0;n Iterator<Integer> ite=set.iterator();n while(ite.hasNext()){n sum2+=ite.next();n }n int result=2*sum2-sum;n return result;n }n}n

補充一種JavaScript採用思想2的寫法，採用reduce只有一行

var singleNumber = function(nums) {n return nums.reduce((res,a)=>res^a,0);n};n

參考資料

LeetCode- Bit Manipulation LeetCode總結（1） —— 位運算：http://blog.csdn.net/xsloop/article/details/47006241

http://blog.csdn.net/zhning12L/article/details/78271157

歡迎加入碼蜂社演算法交流群：天天一道演算法題

掃描下方二維碼或搜素「碼蜂社」公眾號，不怕錯過好文章：

最後求波點贊和關注~