」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > 我們如何在 O(n) 時間和 O(1) 空間內找到從 0 到 n-1 的數字數組中的重複項?

我們如何在 O(n) 時間和 O(1) 空間內找到從 0 到 n-1 的數字數組中的重複項?

發佈於2024-11-08
瀏覽:509

How can we find duplicates in an array of numbers from 0 to n-1 in O(n) time and O(1) space?

在O(n) 時間和O(1) 空間中尋找重複項:深入解釋

提出的問題涉及識別重複項數組中包含0 到n-1 範圍內的數字的元素。挑戰在於如何在 O(n) 時間複雜度內並僅使用恆定 (O(1)) 記憶體空間有效地實現這一目標。

所提出的解決方案採用了一種巧妙的技術,不需要哈希表或其他附加資料結構。相反,它利用數組本身中的值來識別和標記重複元素。

  1. 排列數組:

    內部循環排列基於以下邏輯的數組:

    while A[A[i]] != A[i]
        swap(A[i], A[A[i]])
    end while

    此排列步驟可確保如果陣列中存在元素 x,則其至少一個實例將位於 A[x]。這對於後續步驟至關重要。

  2. 識別重複項:

    外循環檢查每個元素A[i]:

    for i := 0 to n - 1
        if A[i] != i then
            print A[i]
        end if
    end for

    如果 A[i] != i,則表示 i 沒有出現在陣列中正確的位置。因此,它是一個重複元素,並且被印製。

  3. 時間複雜度分析:

    此技術運行時間為 O(n) 時間。巢狀循環有一個迭代 n 次的外循環和一個最多執行 n - 1 次迭代的內循環(因為每次交換都會使一個元素更接近其正確位置)。因此,迭代總數以n*(n - 1) 為界,即O(n^2),但可以簡化為O(n),因為n*(n - 1) = n^2 - n = n(n - 1) = n*n - n

  4. 空間複雜度分析:

    此演算法僅使用恆定空間,與輸入的大小無關。關鍵的見解是用於排列的空間已經存在於輸入數組中。不需要額外的儲存結構。

  5. 附加說明:

    • 附加說明:
    [演算法假設陣列包含從0到n的整數- 1.
即使存在重複項,時間複雜度也保持不變。

How can we find duplicates in an array of numbers from 0 to n-1 in O(n) time and O(1) space? 
此演算法對於小數據是有效的到中等大小的陣列。對於大型數組,使用哈希表等資料結構的替代方法可能更合適。

最新教學 更多>
  • 如何簡化PHP中的JSON解析以獲取多維陣列?
    如何簡化PHP中的JSON解析以獲取多維陣列?
    php 試圖在PHP中解析JSON數據的JSON可能具有挑戰性,尤其是在處理多維數組時。 To simplify the process, it's recommended to parse the JSON as an array rather than an object.To do...
    程式設計 發佈於2025-07-18
  • 如何使用Python的請求和假用戶代理繞過網站塊?
    如何使用Python的請求和假用戶代理繞過網站塊?
    如何使用Python的請求模擬瀏覽器行為,以及偽造的用戶代理提供了一個用戶 - 代理標頭一個有效方法是提供有效的用戶式header,以提供有效的用戶 - 設置,該標題可以通過browser和Acterner Systems the equestersystermery和操作系統。通過模仿像Chro...
    程式設計 發佈於2025-07-18
  • C++中如何將獨占指針作為函數或構造函數參數傳遞?
    C++中如何將獨占指針作為函數或構造函數參數傳遞?
    在構造函數和函數中將唯一的指數管理為參數 unique pointers( unique_ptr [2啟示。通過值: base(std :: simelor_ptr n) :next(std :: move(n)){} 此方法將唯一指針的所有權轉移到函數/對象。指針的內容被移至功能中,在操作...
    程式設計 發佈於2025-07-18
  • 在GO中構造SQL查詢時,如何安全地加入文本和值?
    在GO中構造SQL查詢時,如何安全地加入文本和值?
    在go中構造文本sql查詢時,在go sql queries 中,在使用conting and contement和contement consem per時,尤其是在使用integer per當per當per時,per per per當per. 在GO中實現這一目標的慣用方法是使用fmt.spr...
    程式設計 發佈於2025-07-18
  • CSS強類型語言解析
    CSS強類型語言解析
    您可以通过其强度或弱输入的方式对编程语言进行分类的方式之一。在这里,“键入”意味着是否在编译时已知变量。一个例子是一个场景,将整数(1)添加到包含整数(“ 1”)的字符串: result = 1 "1";包含整数的字符串可能是由带有许多运动部件的复杂逻辑套件无意间生成的。它也可以是故意从单个真理...
    程式設計 發佈於2025-07-18
  • 如何將PANDAS DataFrame列轉換為DateTime格式並按日期過濾?
    如何將PANDAS DataFrame列轉換為DateTime格式並按日期過濾?
    Transform Pandas DataFrame Column to DateTime FormatScenario:Data within a Pandas DataFrame often exists in various formats, including strings.使用時間數據時...
    程式設計 發佈於2025-07-18
  • Spark DataFrame添加常量列的妙招
    Spark DataFrame添加常量列的妙招
    在Spark Dataframe ,將常數列添加到Spark DataFrame,該列具有適用於所有行的任意值的Spark DataFrame,可以通過多種方式實現。使用文字值(SPARK 1.3)在嘗試提供直接值時,用於此問題時,旨在為此目的的column方法可能會導致錯誤。 df.withCo...
    程式設計 發佈於2025-07-18
  • 如何使用PHP將斑點(圖像)正確插入MySQL?
    如何使用PHP將斑點(圖像)正確插入MySQL?
    essue VALUES('$this->image_id','file_get_contents($tmp_image)')";This code builds a string in PHP, but the function call fil...
    程式設計 發佈於2025-07-18
  • 同實例無需轉儲複製MySQL數據庫方法
    同實例無需轉儲複製MySQL數據庫方法
    在同一實例上複製一個MySQL數據庫而無需轉儲在同一mySQL實例上複製數據庫,而無需創建InterMediate sqql script。以下方法為傳統的轉儲和IMPORT過程提供了更簡單的替代方法。 直接管道數據 MySQL手動概述了一種允許將mysqldump直接輸出到MySQL cli...
    程式設計 發佈於2025-07-18
  • Python中嵌套函數與閉包的區別是什麼
    Python中嵌套函數與閉包的區別是什麼
    嵌套函數與python 在python中的嵌套函數不被考慮閉合,因為它們不符合以下要求:不訪問局部範圍scliables to incling scliables在封裝範圍外執行範圍的局部範圍。 make_printer(msg): DEF打印機(): 打印(味精) ...
    程式設計 發佈於2025-07-18
  • 在程序退出之前,我需要在C ++中明確刪除堆的堆分配嗎?
    在程序退出之前,我需要在C ++中明確刪除堆的堆分配嗎?
    在C中的顯式刪除 在C中的動態內存分配時,開發人員通常會想知道是否有必要在heap-procal extrable exit exit上進行手動調用“ delete”操作員,但開發人員通常會想知道是否需要手動調用“ delete”操作員。本文深入研究了這個主題。 在C主函數中,使用了動態分配變量(...
    程式設計 發佈於2025-07-18
  • Java中假喚醒真的會發生嗎?
    Java中假喚醒真的會發生嗎?
    在Java中的浪費喚醒:真實性或神話? 在Java同步中偽裝喚醒的概念已經是討論的主題。儘管存在這種行為的潛力,但問題仍然存在:它們實際上是在實踐中發生的嗎? Linux的喚醒機制根據Wikipedia關於偽造喚醒的文章,linux實現了pthread_cond_wait()功能的Linux實現,...
    程式設計 發佈於2025-07-18
  • 如何從PHP中的數組中提取隨機元素?
    如何從PHP中的數組中提取隨機元素?
    從陣列中的隨機選擇,可以輕鬆從數組中獲取隨機項目。考慮以下數組:; 從此數組中檢索一個隨機項目,利用array_rand( array_rand()函數從數組返回一個隨機鍵。通過將$項目數組索引使用此鍵,我們可以從數組中訪問一個隨機元素。這種方法為選擇隨機項目提供了一種直接且可靠的方法。
    程式設計 發佈於2025-07-18
  • 如何使用組在MySQL中旋轉數據?
    如何使用組在MySQL中旋轉數據?
    在關係數據庫中使用mySQL組使用mySQL組進行查詢結果,在關係數據庫中使用MySQL組,轉移數據的數據是指重新排列的行和列的重排以增強數據可視化。在這裡,我們面對一個共同的挑戰:使用組的組將數據從基於行的基於列的轉換為基於列。 Let's consider the following ...
    程式設計 發佈於2025-07-18
  • PHP SimpleXML解析帶命名空間冒號的XML方法
    PHP SimpleXML解析帶命名空間冒號的XML方法
    在php 很少,請使用該限制很大,很少有很高。例如:這種技術可確保可以通過遍歷XML樹和使用兒童()方法()方法的XML樹和切換名稱空間來訪問名稱空間內的元素。
    程式設計 發佈於2025-07-18

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3