一道有意思的面試演算法題

来源:https://www.cnblogs.com/chenjg/archive/2019/01/04/10218608.html
-Advertisement-
Play Games

新年第一篇文章,先祝大家新年快樂!!那麼接下來進入正文。 前言 前陣子突發奇想,突然開始刷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


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • //組件引入import pager from '../../component/pager/pager.vue' //組件調用聲明components:{ pager} //參數data () { return { pageSize: 30, //總頁數 -- 後臺傳值 pageNo: 2 //當 ...
  • 個人認為:margin是用來隔開元素與元素的間距;padding是用來隔開元素與內容的間隔。margin用於佈局分開元素使元素與元素互不相干;padding用於元素與內容之間的間隔,讓內容(文字)與(包裹)元素之間有一段“呼吸距離”。 ...
  • 總結了一些常見的http的狀態碼,以及常見的解決方案。 一.各範圍內狀態碼大致含義 1xx:臨時響應(Informational),需要請求者繼續執行操作的狀態代碼,表示伺服器正在接受請求。 2xx:成功狀態碼(Success),已成功接受客戶端請求。 3xx:重定向狀態碼(Redirection) ...
  • jQuery 選擇器 jQuery 效果函數 jQuery 文檔操作方法 這些方法對於 XML 文檔和 HTML 文檔均是適用的,除了:html()。 jQuery 屬性操作方法 下麵列出的這些方法獲得或設置元素的 DOM 屬性。 這些方法對於 XML 文檔和 HTML 文檔均是適用的,除了:htm ...
  • isNaN(val) 當val為NaN的時候,isNaN(val)返回ture 當val不為NaN的時候,isNaN(val)返回false ...
  • 居中問題: 1.Fixed定位margin:0 auto;不管用,水平居中需要做如下處理: position: fixed; top: 0; bottom: 0; left: 0; right: 0; margin: auto; 2.relative定位margin:0 auto;管用,水平居中需要 ...
  • 本文由雲+社區發表 在一線做了十年的開發,經歷了網易、百度、騰訊研究院、MIG 等幾個地方,陸續做過 3D 游戲、2D 頁游、瀏覽器、移動端翻譯 app 等。 積累了一些感悟。必然有依然幼稚的地方,就當拋磚引玉,聊為笑談。 一、對於團隊而言,流程太重要了 行軍打仗,你需要一個嚮導;如果沒有嚮導,你需 ...
  • 本文記錄在自己學習js過程中,違反直覺,出乎意料,倍感震驚的知識點。當然,不瞭解這個知識點,很容易出錯,因為畢竟違反直覺,出乎意料,倍感震驚嘛! 1. 兩個內容一樣的數組竟然不相等? 知識點:對象引用,更詳細的介紹點這裡 2. 我們都知道,0.1+0.2等於0.3,但是js中 0.1+0.2 不等於 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...