前端JavaScript算法找出隻出現一次的數字
題目:隻出現一次的數字
給定一個非空整數數組,除瞭某個元素隻出現一次以外,其餘每個元素均出現兩次。找出那個隻出現瞭一次的元素。
說明:
你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎?
示例 1:
輸入: [2,2,1]
輸出: 1示例 2:
輸入: [4,1,2,1,2]
輸出: 4
解:
第一個反應用 map 來解,時間復雜度 O(n),是線性的,滿足題意,隻不過空間復雜度消耗是 O(n),怎樣降低空間復雜度,在方法二中講;
解法一:用 map 來解:
/** * @param {number[]} nums * @return {number} */ var singleNumber = function(nums) { let map = new Map(); for(let i = 0; i<nums.length;i++){ if(map.has(nums[i])){ map.set(nums[i],map.get(nums[i])+1); }else{ map.set(nums[i],1) } } for(let [key,value] of map.entries()){ if(value===1){ return key } } };
解法二:用 異或 解
重點當然就是在怎麼理解:不使用額外空間來實現
其實就是就要在數組本身上進行操作,異或操作可以幫助我們實現這一點;
異或(eor)是一個數學運算符。它應用於邏輯運算。兩個相等的數異或為0;兩個值不相同,則異或結果為1;一個不為0的數與0異或為這個數本身;
/** * @param {number[]} nums * @return {number} */ var singleNumber = function(nums) { for (var i = 1; i < nums.length; i++) { nums[0] = nums[0] ^ nums[i]; // 把所有的元素都異或到nums[0]上。 } return nums[0]; };
以上就是前端JavaScript算法找出隻出現一次的數字的詳細內容,更多關於JavaScript算法隻出現一次數字的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- 前端JavaScript多數元素的算法詳解
- C++實現LeetCode(137.單獨的數字之二)
- C++LeetCode數據結構基礎詳解
- Java算法練習題,每天進步一點點(2)
- go語言題解LeetCode88合並兩個有序數組示例