目錄[隱藏][顯示]
- 1.如何定義數組?
- 2. 動態數組:它們是什麼? 它們與基本數組有何不同?
- 3. 數組和字典有何不同?
- 4. 列出數組的一些優點和缺點。
- 5.“稀疏數組”指的是什麼?
- 6. 什麼時候你會選擇鍊錶而不是數組?
- 7. 索引數組與關聯數組有何區別?
- 8.Heap相對於排序數組有什麼優勢?
- 9. 我們可以將數組的大小定義為負數嗎?
- 10. 如何在 1 到 100 個元素的數組中找到丟失的整數?
- 11. 如何查找數組中元素的索引?
- 12. 如何從數組中刪除特定元素?
- 13. 如何驗證兩個數組相等?
- 14. 當我們討論數組時,“維度”和“下標”是什麼意思?
- 編碼面試問題
- 15. 在數組中查找具有指定總和的一對
- 16.線性時間的二進制數組排序
- 17. 查找數組中最大的二整數乘積。
- 18. 如何將數組的所有零移到末尾
- 19. 如何對具有在一次操作中交換的兩個條目的數組進行排序。
- 20. 如何就地組合兩個已排序的數組。
- 21. 如何對交替高位和低位的數組進行重新排序?
- 22. 如何在不使用除法運算符的情況下將數組中的每個元素替換為數組中每個元素的乘積?
- 23. 在對數時間內找到數組中最奇數的元素
- 24. 如何獲取循環數組中每個元素後續較大的元素?
- 25. 查找數組的反轉計數?
- 26. 什麼是雨水收集問題?
- 結論
編碼面試包含一系列 DSA 問題。 如果您正在準備即將接受 FAANG 或其他一級技術公司的技術面試,那麼您應該熟練掌握數組。
在大多數編碼面試中,它排在第二位,僅次於字符串。 數組是一組在內存中彼此靠近的相關數據元素。
由於它們連接到所有編程語言,例如 C、C++、Java、Python、Perl 和 Ruby,因此它們無處不在。 繼續閱讀一些基於數組的練習編碼挑戰以及面試問題和答案。
本文將使用 Python 來解決編碼問題,因為它易於使用、理解,並且我們大多數人都熟悉。
讓我們開始。
1.如何定義數組?
- 一組相關的數據類型就是一個數組。
- 數組總是固定的。
- 同一種變量通過數組對象存儲在多個地方。
- 原始類型和對象引用都與其兼容。
2. 動態數組:它們是什麼? 它們與基本數組有何不同?
動態數組(在 Java 中也稱為可增長數組、可調整大小數組、可更改數組或 ArrayList)提供的自動縮放功能是一個顯著的優勢。
由於數組具有固定大小,因此您必須始終提前知道數組將存儲多少個元素。 另一方面,動態數組會隨著向其中添加其他成員而增長,因此您無需事先知道其確切大小。
3. 數組和字典有何不同?
這是一系列經常被問到的基於基礎知識的面試問題。 以下是數組和字典之間的主要區別:
- 數組是相似項的有序列表。 另一方面,字典具有鍵值對。
- 數組大小可以動態改變。 字典中不存在這種動態的想法。
- 在使用數組之前,必須指定其大小。 字典大小不需要定制。
- 如果您希望擴展數組的大小,請使用 Redim 語句。 在字典中,無需聲明即可添加元素。
4. 列出數組的一些優點和缺點。
優點:
- 數組可以同時對多個元素進行排序。
- 其他 數據結構,就像堆棧、隊列、鍊錶、樹、圖等一樣,可以在數組中實現。
- 索引可用於到達數組的元素。
缺點:
- 數組的大小必須提前聲明。 然而,在聲明數組時,我們可能不知道我們需要的大小。
- 數組的結構是靜態的。 這意味著數組大小始終是固定的,並且內存分配不能增加或減少。
5.“稀疏數組”指的是什麼?
稀疏數組是具有許多零值條目的數據數組。 相反,密集數組包含大部分具有非零值的項目。 將數字轉換為對象的稀疏數組的索引可能包含間隙。 與 HashMap 相比,它們的內存效率更高。
6. 什麼時候你會選擇鍊錶而不是數組?
當使用鍊錶而不是數組時,請考慮:
- 您不需要任何元素即可進行隨機訪問。
- 在時間可預測性至關重要的情況下,您需要在列表中進行恆定時間的插入和刪除。
- 為了創建優先級隊列,您可能需要將項目放置在列表的中心。
- 你不知道這個清單會有多長。 如果數組大小增加,則必須重新聲明並複制內存,就像簡單數組一樣。
7. 索引數組與關聯數組有何區別?
下表列出了關聯數組和索引數組之間的主要區別。
- 文本或數字格式的鍵值對用於對關聯數組進行排序。 索引數組的鍵都是數字,每個鍵都連接到一個不同的值。
- 在關聯數組中,鍵可能是字符串。 具有從 0 開始的整數鍵的索引數組。
- 兩列表格模仿關聯數組的行為。 索引數組與單列表類似。
- 地圖是關聯數組類型。 索引數組不是映射。
8.Heap相對於排序數組有什麼優勢?
使用堆相對於排序數組的時間效率是主要優勢。 雖然堆操作速度更快,但對數組進行排序需要大量時間。 堆發現最小元素的速度比數組排序的速度要快得多。
可以使用排序數組以兩種方式之一排列給定的數字集合。 另一方面,對於給定的數字集合,可能存在多個潛在堆。
9. 我們可以將數組的大小定義為負數嗎?
不,我們不能將負整數定義為數組的大小。 如果我們聲明的話,就不會出現編譯時錯誤。 然而,在運行時,我們會遇到 NegativeArraySizeException。
10. 如何在 1 到 100 個元素的數組中找到丟失的整數?
系列的總和可以通過應用以下函數來計算:n (n + 1) / 2
僅當數組沒有任何重複項或缺少多個整數時,此函數才會運行。 數組是否有重複元素,可以對數組進行排序,看看是否有相同的元素。
11. 如何查找數組中元素的索引?
可以通過線性或二分搜索來發現元素的索引。 線性搜索函數會循環遍歷數組中的每個元素,直到找到所需元素的匹配項。 一旦找到匹配的元素,它就會返回索引。 因此,線性搜索的時間複雜度為O.(n)。 已排序和未排序的數組都可以使用線性搜索。
使用二分搜索,不斷將數組分成兩半,直到間隔的中位數與所需元素匹配並提供索引,如果數組已排序,則可以獲得元素的索引。 因此,二分查找的時間複雜度為O(log n)。
12. 如何從數組中刪除特定元素?
由於您不能簡單地從原始數組中刪除元素,因為它們是具有定義大小的固定集,因此面試官正在尋求您建議不同的方法並處理問題提出的問題。 最好的做法是創建一個新數組以便刪除元素。 您可以將第一個數組中的元素複製到該數組中,並且僅包含要刪除的元素。
另一種策略是在數組中查找目標元素,然後反轉目標元素右側所有項目的順序。
13. 如何驗證兩個數組相等?
您必須首先驗證提供的兩個數組的長度。 當兩個數組的匹配項的長度相等時,對它們進行比較。 兩個數組將被視為相等。 如果每個對應關係中的每對分量都相等。 如果數組很大,不建議使用此方法檢查兩個數組的相等性,因為這會花費大量時間。 您還可以使用 Arrays 類中包含的 equals() 方法,但是,如果面試官要求您在不使用內置方法的情況下比較兩個數組,那麼這種方法會很有用。
14. 當我們討論數組時,“維度”和“下標”是什麼意思?
數組的“維度”是識別每個單獨成員所需的索引或下標的數量。 下標和尺寸可能不清楚。 維度是對允許的鍵範圍的描述,而下標是數字。 每個數組維度只需要一個下標。
例如,數組 arr[10][5] 具有二維。 一件尺寸為 10,另一件尺寸為 5。 要尋址其組件,您需要兩個下標。 兩者都在 0 到 4 之間; 0 到 9 之間的一個(含 XNUMX 和 XNUMX)。
編碼面試問題
15. 在數組中查找具有指定總和的一對
例如,
輸入:
- 數字 = [8, 7, 2, 5, 3, 1]
- 目標= 10
輸出:
- 已找到一對 (8, 2)
- Or
- 已找到一對 (7, 3)
輸入:
- 數字 = [5, 2, 6, 8, 1, 9]
- 目標= 12
輸出:
- 未找到配對
16.線性時間的二進制數組排序
在線性時間和固定區域內對二進制數組進行排序。 輸出應該首先顯示全零,然後顯示全XNUMX。
例如,
- 輸入:{ 1, 0, 1, 0, 1, 0, 0, 1 }
- 輸出:{0}
一種簡單的方法是計算數組中 0 的總數,例如 k,然後用 0 填充數組中的前 k 個索引,用 1 填充其餘索引。作為替代方案,我們可以計算數組中總共有多少個 1數組 k,將數組中的最後 k 個索引填充為 1,其餘索引填充為 0。
給定方法的時間複雜度為 O(n),並且不使用額外的存儲,其中 n 是輸入的大小。
17. 查找數組中最大的二整數乘積。
求整數數組中兩個數字的最大乘積。
以數組 10 3 5 6 2 為例。 (-10, -3) 或 (5, 6) 對是最高的乘積。
考慮每一個元素的組合併找出他們的產品是一種愚蠢的做法。 如果當前對的乘積大於迄今為止獲得的最大乘積,則更新最大乘積。 最後打印最終產品的組件。
上面的解決方案,其中n是輸入量,時間複雜度為O(n2),並且不佔用更多空間。
18. 如何將數組的所有零移到末尾
將整數數組中的所有零移至末尾。 答案應該避免使用常量空間並保留數組組件的相對順序。
輸入:{1,2,3,0,8,0,4,7,XNUMX}
輸出將為 {1,2,3,8,4,7,0,0}
如果當前元素不為零,則將該元素放在數組中的以下可用位置。 處理完數組的所有項目後,用 0 填充所有剩餘索引。
上述解決方案的時間複雜度為 O(n),其中 n 是輸入的大小。
19. 如何對具有在一次操作中交換的兩個條目的數組進行排序。
給定兩個交換項和所有元素按升序排列的數組,在線性時間內對數組進行排序。 假設該數組不包含重複項。
輸入:= [1,9,3,4,7,2] 或 [9,3,7,2,1,4] 或 [2,4,1,7,3,9]
輸出:= [1,2,3,4,7,9]
從數組中的第二個元素開始,目標是將每個元素與其前一個元素進行比較。 爭議的位置通過兩個指針 x 和 y 來存儲。
如果前者大於後者,則將 x 更新為前一個元素的索引,將 y 更新為當前元素的索引。 如果發現前一個元素大於當前元素,則將 y 更新為當前元素的索引。
最後,一旦我們處理完每對相鄰元素,就交換索引 x 和 y 處的元素。
由於上述方法僅對大小為n的輸入數組執行一次掃描,因此其時間複雜度為O(n)。 該解決方案不需要額外的空間。
20. 如何就地組合兩個已排序的數組。
合併數組 X[] 和 Y[](兩個大小分別為 m 和 n 的已排序數組)的項目,方法是保留排序順序,即用前 m 個最小元素填充 X[],並用前 m 個最小元素填充 Y[]。剩餘元素。
如果數組 X[] 中的某個元素已經位於正確位置(即剩餘元素中最小的元素),則忽略它; 否則,用最小的元素替換它,該元素也恰好是 Y[] 的第一個成員。 要在交換後保留排序順序,請將元素(現在位於 Y[0])傳輸到 Y[] 中的正確位置。
第一個數組的大小為 m,第二個數組的大小為 n,時間複雜度為 O(mn)。
21. 如何對交替高位和低位的數組進行重新排序?
重新排列整數數組,使每個後續成員都大於前面和後面的元素。 假設數組不包含任何重複元素。
對於有效的方法來說,對數組進行排序或利用額外的空間並不是必需的。 該計劃首先是數組的第二個成員,並且每次循環迭代都會增加兩個成員。
如果最後一個元素超過第一個元素,則交換組件。 同樣,如果後續元素大於當前元素,則切換這兩個項目。 我們將在循環結束時獲得符合指定限制的所需數組。
22. 如何在不使用除法運算符的情況下將數組中的每個元素替換為數組中每個元素的乘積?
不使用除法運算符,將整數數組中的每個元素替換為所有其他元素的乘積。
在線性時間和常數空間中,我們可以利用遞歸來解決這個問題。 遞歸計算右子數組中每個元素的乘積並將左子數組乘積作為函數參數傳遞是這樣的概念。
時間複雜度為O(n)。
23. 在對數時間內找到數組中最奇數的元素
給定一個整數數組,其中除一個成員之外的所有成員都出現偶數次,問題是確定該元素出現了多少次。 如果相同的元素在數組中成對出現,並且一行中給定元素的實例永遠不會超過兩個,則在對數時間和常數空間中查找奇數出現的元素。
XOR 運算使我們能夠在線性時間內解決這個問題。 目標是對數組中的每個元素進行異或。 偶數出現的元素相互抵消後,僅剩下奇數出現的元素。
這個問題甚至可以在 O(log(n)) 時間內解決。
24. 如何獲取循環數組中每個元素後續較大的元素?
應找到循環整數數組中每個元素的下一個較大元素。 數組中元素 x 之後的第一個較大整數是該元素的後續較大元素。
從右到左,我們可以對數組項進行操作。 目標是循環每個元素 x 直到堆棧為空或者頂部有更高的元素。 當 x 出現時,將下一個更大的元素設置為出現在堆棧頂部。
25. 查找數組的反轉計數?
求數組反轉的總數。 如果 I j) 和 (A[i] > A[j]),則一對 I j) 被稱為數組 A 的反轉。 我們必須計算數組中的每一對。
計算右側所有少於它的數組成員並將結果添加到輸出中是一種簡單的方法。
該解決方案的複雜度為 O(n2),其中 n 是輸入的大小。
26. 什麼是雨水收集問題?
找到一組給定的寬度為一個單位的條中可以捕獲的最多水量被稱為“捕獲降雨”問題。
目標是確定可以放置在每個條形左側和右側的最高條形。 左右前導條的最小值減去當前條的高度,就是每個條頂部存儲的水量。
結論
與其他數據結構主題相比,數組更簡單。 為了解決數組面試問題,您需要對數組有一個基本的了解。
您應該廣泛回顧數組的基礎知識,包括數組操作(從聲明/創建數組到訪問/修改數組項),以及循環、遞歸和基本運算符等編程概念,以便成功回答數組面試問題。 徹底認識到這個問題。
如果您有任何疑問,請尋求澄清。 考慮將問題分成更易於管理的部分。 在開始編程之前,請確保您已經記住了算法; 將其寫下來或在流程圖中可視化。 然後開始編寫代碼。
發表評論