日拱算法:只出現一次的數字

語言: CN / TW / HK

持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第26天,點擊查看活動詳情


xixixi,更文無力,轉攻算法簡單題。中難題畏畏縮縮,簡單題我重拳出擊~~

image.png

突一突 LeetBook 列表/算法面試題彙總

沖沖衝~~

題目:### 只出現一次的數字

給定一個非空整數數組,除了某個元素只出現一次以外,其餘每個元素均出現兩次。找出那個只出現了一次的元素。

説明:

你的算法應該具有線性時間複雜度。 你可以不使用額外空間來實現嗎?

``` 示例 1:

輸入: [2,2,1] 輸出: 1

示例 2:

輸入: [4,1,2,1,2] 輸出: 4 ```

解:

重點當然就是在怎麼理解:不使用額外空間來實現

其實就是就要在數組本身上進行操作;

解法一:用 map 來解:

```js /* * @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 } }

}; ```

image.png

解法二:用 異或 解

異或(eor)是一個數學運算符。它應用於邏輯運算。兩個相等的數異或為0;兩個值不相同,則異或結果為1;一個不為0的數與0異或為這個數本身;

js /** * @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]; };

image.png

OK,以上便是本篇分享。點贊關注評論,為好文助力👍

我是掘金安東尼 🤠 100 萬閲讀量人氣前端技術博主 💥 INFP 寫作人格堅持 1000 日更文 ✍ 關注我,陪你一起度過漫長編程歲月 🌏