新年第一篇文章,先祝大家新年快樂!!那麼接下來進入正文。 前言 前陣子突發奇想,突然開始刷leetcode。其中刷到了一道有意思的題目,發現這道題是當時秋招的時候,騰訊面試官曾經問過我的題目。於是分享給大家看下。 題目描述 給定一個 非空 整數數組,除了某個元素只出現一次以外,其餘每個元素均出現兩次 ...
新年第一篇文章,先祝大家新年快樂!!那麼接下來進入正文。
前言
前陣子突發奇想,突然開始刷leetcode。其中刷到了一道有意思的題目,發現這道題是當時秋招的時候,騰訊面試官曾經問過我的題目。於是分享給大家看下。
題目描述
給定一個非空整數數組,除了某個元素只出現一次以外,其餘每個元素均出現兩次。找出那個只出現了一次的元素。
初步解法
這道題第一眼看過去,思路挺簡單的,我們只需要維護一個對象來記錄每一個元素出現的次數,使用元素的值作為key,元素出現的次數作為value。之後再遍歷這個對象,找到value為1的key。對應的key就是那個元素。代碼如下:
function singleNumber(nums) {
const obj = {};
for (let i = 0; i < nums.length; i++) {
obj[nums[i]] = obj[nums[i]] ? obj[nums[i]] + 1 : 1;
}
for (let key in obj) {
if (obj[key] === 1) {
return Number(key); // 由於 key 是 string ,因此我們這裡需要轉化下
}
}
}
console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8])); // 8
增加限制
是吧,這道題很簡單,那我為什麼要說它有意思呢?
因為題目裡面其實還有一個限制:
你的演算法應該具有線性時間複雜度。 你可以不使用額外空間來實現嗎?
重點在於不使用額外空間。我們上面那種解法,創建了一個新的對象來儲存結果,明顯是不行的。那麼有沒有辦法可以只使用原來的數組來實現這個功能呢?
最終解法
我們可以思考下,一個數組裡,所有的數字都出現兩次,除了一個我們要找的數字只出現一次。那麼,我們有沒有辦法將兩個相同的數字給過濾掉呢?
好啦,不賣關子了,之前有瞭解過的人應該就知道解決方案了,如果之前沒瞭解過這方面東西的人,可以繼續往下看。
解決方案:異或操作
異或運算是對於二進位數字而言的,比如說一個有兩個二進位a、b,如果a、b兩個值不相同,則異或結果為1。如果a、b兩個值相同,異或結果為0。
而javascript的按位異或(即^操作)操作,則會對兩個數字相應的每一對比特位執行異或操作。
比如說 1 ^ 2,本質上其實是1和2的每一對比特位執行異或操作,等價於下麵
00000000000000000000000000000001 // 數字1對應的二進位
^ 00000000000000000000000000000010 // 數字2對應的二進位
= 00000000000000000000000000000011 // 數字3對應的二進位
因此1^2的結果就為3啦。
那麼如果兩個相同的數字進行異或操作,結果就可想而知,答案為0啦。
如果是0和任何一個數字異或呢?結果是數字本身。
這樣一來的話,我們是不是有了這個問題的解決辦法了?我們只需要遍曆數組,將所有的值取異或,最終剩下的值,就是那個只出現一次的數字。代碼如下:
/**
* 只存在一次的數字
* https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/
* @param {number[]} nums
* @return {number}
*/
function singleNumber(nums) {
for (let i = 1; i < nums.length; i++) {
nums[0] ^= nums[i];
}
return nums[0];
};
console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8]));
結語
這道面試題主要考驗面試者對異或的理解,以及能不能活學活用,將這道題與異或聯繫在一起。當然,最重要的還是多學習、多刷題、多看書。這樣才能不斷進步。
本文地址在->本人博客地址, 歡迎給個 start 或 follow