點擊上方藍(lán)字設(shè)為星標(biāo)

每周一、三、五上午 8:30 準(zhǔn)時推送

下面開始今天的學(xué)習(xí)～

面試中的算法問題，有很多并不需要復(fù)雜的數(shù)據(jù)結(jié)構(gòu)支撐。就是用數(shù)組，就能考察出很多東西了。其實，經(jīng)典的排序問題，二分搜索等等問題，就是在數(shù)組這種最基礎(chǔ)的結(jié)構(gòu)中處理問題的，今天主要介紹力扣(LeetCode)中典型的數(shù)組類問題，主要介紹這類問題的一些常用解法：做好初始定義；基礎(chǔ)算法思想應(yīng)用；對撞指針；滑動窗口法等。所有題解代碼采用 Python 實現(xiàn)。

做好初始定義

做數(shù)組類算法問題的時候，我們常常需要定義一個變量，明確該變量的定義，并且在書寫整個邏輯的時候，要不停的維護(hù)住這個變量的意義。也特別需要注意初始值和邊界的問題。

283. 移動零

題目描述

給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。

示例：

輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]

說明：

• 必須在原數(shù)組上操作，不能拷貝額外的數(shù)組。

• 盡量減少操作次數(shù)。

直觀解題思路

首先遍歷一遍數(shù)列，用另個數(shù)列按順序存儲所有非 0 的元素，在將存儲的非零元素按順序復(fù)制到原數(shù)列中，空位補(bǔ) 0 即可。

直觀的解題思路新建額外的數(shù)組，不符合要求，但是對于我們下面的優(yōu)化算法很有起始。

簡單的優(yōu)化

只要把數(shù)組中所有的非零元素，按順序給數(shù)組的前段元素位賦值，剩下的全部直接賦值 0。我們定義一個 nums 0...i?表示為非 0 元素的數(shù)組，之后在遍歷數(shù)列的時候不斷維護(hù)這個定義.

代碼實現(xiàn)

class?Solution:

? def?moveZeroes(self,?nums):

? ? """

? ? ? :type nums: List[int]

? ? ? :rtype: void Do not return anything, modify nums in-place instead.

? ??"""

? ? n?=?len(nums)

? ? i?=?-1

? ? j?=?0

? ? # nums[0....i]表示非0元素的數(shù)列,初始值i=-1

? ? while?j?<=?n-1:

? ? ? if?nums[j]?!=?0:

? ? ? ? i?+=?1

? ? ? ? nums[i]?=?nums[j]

? ? ? j?+=?1

? ? for?k?in?range(i+1,?n):

? ? ? nums[k]?=?0

相似問題：

27. 移除元素

題目描述

給定一個數(shù)組 nums 和一個值 val，你需要原地移除所有數(shù)值等于 val 的元素，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。

示例 1:

給定 nums?=?[3,2,2,3],?val?=?3,

函數(shù)應(yīng)該返回新的長度?2,?并且 nums 中的前兩個元素均為?2。

你不需要考慮數(shù)組中超出新長度后面的元素。

...

解題思路

定義 nums[0...i] 為非 val 的數(shù)列，遍歷整個數(shù)列不斷的維護(hù)這個定義

代碼實現(xiàn)

class?Solution:

? def?removeElement(self,?nums,?val):

? ? """

? ? :type nums: List[int]

? ? :type val: int

? ? :rtype: int

? ??"""

? ? n?=?len(nums)

? ? i?=?-1

? ? # 定義nums[0...i]為非val的數(shù)列

? ? j?=?0

? ? while?j?<=?n-1:

? ? ? if?nums[j]?!=?val:

? ? ? ? i?+=?1

? ? ? ? nums[i]?=?nums[j]

? ? ? j?+=?1

? ? return?i+1

26. 刪除排序數(shù)組中的重復(fù)項

題目描述

給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

示例 1:

給定數(shù)組 nums?=?[1,1,2],

函數(shù)應(yīng)該返回新的長度?2,?并且原數(shù)組 nums 的前兩個元素被修改為?1,?2。

你不需要考慮數(shù)組中超出新長度后面的元素。

...

解題思路

定義 nums[0...i] 為為非重復(fù)數(shù)列，遍歷整個數(shù)列不斷的維護(hù)這個定義。

代碼實現(xiàn)

class?Solution:

? def?removeDuplicates(self,?nums):

? ? """

? ? :type nums: List[int]

? ? :rtype: int

? ??"""

? ? n?=?len(nums)

? ? if?n?==?0?or?n?==1:

? ? ? return?n

? ? # nums[0,i]為非重復(fù)數(shù)列

? ? i?=?0

? ? j?=?i?+?1

? ? while?j?<=?n-1:

? ? ? if?nums[j]?!=?nums[i]:

? ? ? ? # 指向同一個元素不需要賦值

? ? ? ? if?i?+?1?!=?j:

? ? ? ? ? nums[i+1]?=?nums[j]

? ? ? ? i?+=?1

? ? ? j?+=?1

? ? return?i?+?1

80. 刪除排序數(shù)組中的重復(fù)項 II

題目描述

給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素最多出現(xiàn)兩次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

示例 1:

給定 nums?=?[1,1,1,2,2,3],

函數(shù)應(yīng)返回新長度 length?=?5,?并且原數(shù)組的前五個元素被修改為?1,?1,?2,?2,?3?。

你不需要考慮數(shù)組中超出新長度后面的元素。

解題思路

定義 nums[0...i] 滿足每個元素最多出現(xiàn)兩次，初始值 i=-1，遍歷整個數(shù)列不斷的維護(hù)這個定義。

代碼實現(xiàn)

class?Solution:

? def?removeDuplicates(self,?nums):

? ? """

? ? :type nums: List[int]

? ? :rtype: int

? ??"""

? ? n?=?len(nums)

? ? if?(n?<=?2):

? ? ? return?n

? ? # nums[0...i]是符合要求的，

? ? i?=?1

? ? k?=?i?-?1

? ? j?=?i?+?1

? ? while?j?<=?n-1:

? ? ? if?(nums[j]?!=?nums[i])?or?(nums[j]?==?nums[i]?and?nums[j]?!=?nums[k]):

? ? ? ? k?=?i

? ? ? ? nums[i+1]?=?nums[j]

? ? ? ? i?+=?1

? ? ? j?+=?1

? ? return?i?+?1

基礎(chǔ)算法思想在力扣中的應(yīng)用

典型的排序算法思想、二分查找思想在解力扣題目時很有用。

75. 顏色分類

題目描述

給定一個包含紅色、白色和藍(lán)色，一共 n 個元素的數(shù)組，原地對它們進(jìn)行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍(lán)色順序排列。此題中，我們使用整數(shù) 0、 1 和 2 分別表示紅色、白色和藍(lán)色。

注意:

不能使用代碼庫中的排序函數(shù)來解決這道題。

示例:

輸入:?[2,0,2,1,1,0]

輸出:?[0,0,1,1,2,2]

...

解題思路

基數(shù)排序法

可以采用基數(shù)排序法的思想，用一個數(shù)組記錄下 0，1，3 的次數(shù)，后重排，這個算法對數(shù)組進(jìn)行了兩次遍歷，其實有一種只進(jìn)行一次遍歷的方法。

三路快速排序方法

設(shè)置三個 lt, gt, i 定義：nums[0...lt] == 0，nums[lt+1...i-1] = 1，nums[gt...n-1] == 2，遍歷一遍改數(shù)列保持這個定義。

代碼實現(xiàn)

class?Solution:

? def?sortColors(self,?nums):

? ? n?=?len(nums)

? ? lt?=?-1

? ? gt?=?n

? ? i?=?0

? ? while?i?<?gt:

? ? ? if?nums[i]?==?0:

? ? ? ? lt?+=?1

? ? ? ? nums[lt],?nums[i]?=?nums[i],?nums[lt]

? ? ? ? i?+=?1

? ? ? elif?nums[i]?==?2:

? ? ? ? gt?-=?1

? ? ? ? nums[gt],?nums[i]?=?nums[i],?nums[gt]

? ? ? else:

? ? ? ? i?+=?1

215. 數(shù)組中的第 K 個最大元素

題目描述

在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

示例 1:

輸入:?[3,2,1,5,6,4]?和 k?=?2

輸出:?5

...

解題思路

利用快速排序的思想，從數(shù)組 S 中隨機(jī)找出一個元素 X，把數(shù)組分為兩部分 Sa 和 Sb。Sa 中的元素大于等于 X，Sb 中元素小于 X。這時有兩種情況：

• Sa 中元素的個數(shù)小于 k，則 Sb 中的第 k-|Sa| 個元素即為第k大數(shù)；

• Sa 中元素的個數(shù)大于等于 k，則返回 Sa 中的第 k 大數(shù)。時間復(fù)雜度近似為 O(n)

代碼實現(xiàn)

class?Solution:

? # 采用快速排序方法，分成的數(shù)列左邊大于右邊

? def?findKthLargest(self,?nums,?k):

? ? n?=?len(nums)

? ? if?(k?>?n):

? ? ? return

? ? index?=?self.quickSort(nums,?0,?n-1,?k)

? ? return?nums[index]

? def?quickSort(self,?nums,?l,?r,?k):

? ? if?l?>=?r:

? ? ? return?l

? ? p?=?self.partition(nums,?l,?r)

? ? if?p?+?1?==?k:

? ? ? return?p

? ? if?p?+?1?>?k:

? ? ? return?self.quickSort(nums,?l,?p?-1,?k)

? ? else:

? ? ? return?self.quickSort(nums,?p?+?1,?r,?k)

? def?partition(self,?nums,?l,?r):

? ? v?=?nums[l]

? ? j?=?l

? ? i?=?l?+?1

? ? while?i?<=?r:

? ? ? if?nums[i]?>=?v:

? ? ? ? nums[j+1],nums[i]?=?nums[i],nums[j+1]

? ? ? ? j?+=?1

? ? ? i?+=?1

? ? nums[l],?nums[j]?=?nums[j],?nums[l]

? ? return?j

相似問題：

88. 合并兩個有序數(shù)組

題目描述

給定兩個有序整數(shù)數(shù)組 nums1 和 nums2，將 nums2 合并到 nums1 中，使得 num1 成為一個有序數(shù)組。

說明:

• 初始化 nums1 和 nums2 的元素數(shù)量分別為 m 和 n。

• 你可以假設(shè) nums1 有足夠的空間(空間大小大于或等于 m + n)來保存 nums2 中的元素。

...

解題思路

常規(guī)解題思路

其實這道題就是歸并排序 partition 的過程(將兩個有序的數(shù)列合并成一個有序數(shù)列)， 直觀的思路是新建一個新的數(shù)列，遍歷 nums1 和 nums2 這兩個數(shù)列，將新建的數(shù)列有序后又賦值給 nums1 后返回。其實還有一種方法不需要開辟新的空間。

尾插法

由于 nums1 有足夠的空間(空間大小大于或等于 m + n)來保存 nums2 中的元素，所以從 k=m+n-1 開始，分別遍歷 nums1[m...0] 和 nums2[n...0] 中選取值大的。

代碼實現(xiàn)

class?Solution:

? def?merge(self,?nums1,?m,?nums2,?n):

? ? # 尾插入法

? ? if?(n?<?1):

? ? ? return

? ? if?(m?<?1):

? ? ? nums1[0:n]?=?nums2[0:n]

? ? ? return

? ? k?=?m?+?n?-?1

? ? i?=?m?-?1

? ? j?=?n?-?1

? ? while?k?>=?0:

? ? ? if?(nums1[i]?>?nums2[j]?and?i?>=?0)?or?(j?<?0?and?i?>=?0):

? ? ? ? nums1[k]?=?nums1[i]

? ? ? ? k?-=?1

? ? ? ? i?-=?1

? ? ? if?(nums2[j]?>=?nums1[i]?and?j?>=?0)?or?(i?<?0?and?j?>=0):

? ? ? ? nums1[k]?=?nums2[j]

? ? ? ? k?-=?1

? ? ? ? j?-=?1

雙索引技術(shù)-對撞指針

有一些力扣題目，我們可以采用對撞指針進(jìn)行求解：指針 i 和 j 分別指向數(shù)組的第一個元素和最后一個元素，然后指針 i 不斷向前， 指針 j 不斷遞減，知道 i = j(當(dāng)然具體的邏輯操作根據(jù)題目的變化而變化)。

167. 兩數(shù)之和 II - 輸入有序數(shù)組

題目描述

給定一個已按照升序排列 的有序數(shù)組，找到兩個數(shù)使得它們相加之和等于目標(biāo)數(shù)。 函數(shù)應(yīng)該返回這兩個下標(biāo)值 index1 和 index2，其中 index1 必須小于 index2。

說明:

• 返回的下標(biāo)值(index1 和 index2)不是從零開始的。

• 你可以假設(shè)每個輸入只對應(yīng)唯一的答案，而且你不可以重復(fù)使用相同的元素。

...

暴力解法

雙層遍歷，時間復(fù)雜度為 O(n^2)，暴力解法沒有充分利用原數(shù)組的性質(zhì) —— 有序，本文不采用。

當(dāng)我們看到數(shù)列有序的時候，就應(yīng)該想到可以用二分搜索法

二分搜索法

遍歷每個 nums[i]，在剩余數(shù)組中查找 target-nums[i] 的值，時間復(fù)雜度為 O(n log n)。

有興趣的讀者可以用這種方法嘗試一下，應(yīng)該也是可以AC的， 本文采用對撞指針法。

對撞指針法

們首先判斷首尾兩項的和是不是 target，如果比 target 小，那么我們左邊 (i)+1 位置的數(shù)(比左邊位置的數(shù)大)再和右相相加，繼續(xù)判斷。如果比 target 大，那么我們右邊 (j)-1 位置的數(shù)(比右邊位置的數(shù)小)再和左相相加，繼續(xù)判斷。我們通過這樣不斷放縮的過程，就可以在 O(n) 的時間復(fù)雜度內(nèi)找到對應(yīng)的坐標(biāo)位置。

代碼實現(xiàn)

class?Solution:

? def?twoSum(self,?numbers,?target):

? ? n?=?len(numbers)

? ? if?(n?<?2):

? ? ? return?[]

? ? i?=?0

? ? j?=?n-1

? ? while?i?<?j:

? ? ? if?numbers[i]?+?numbers[j]?==?target:

? ? ? ? return?[i+1,j+1]

? ? ? elif?numbers[i]?+?numbers[j]?<?target:

? ? ? ? i?+=?1

? ? ? else:

? ? ? ? j?-=?1

? ? return?[]

相似問題：

125. 驗證回文串

題目描述

給定一個字符串，驗證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫。

說明：本題中，我們將空字符串定義為有效的回文串。

...

解題思路

采用對撞指針

代碼實現(xiàn)

class?Solution:

? def?isPalindrome(self,?s):

? ? """

? ? :type s: str

? ? :rtype: bool

? ??"""

? ? n?=?len(s)

? ? i?=?0

? ? j?=?n-1

? ? while?i?<?j:

? ? ? if?s[i].isalnum()?==?False:

? ? ? ? i?+=?1

? ? ? ? continue

? ? ? if?s[j].isalnum()?==?False:

? ? ? ? j?-=?1

? ? ? ? continue

? ? ? if?s[i].lower()?!=?s[j].lower():

? ? ? ? return?False

? ? ? i?+=?1

? ? ? j?-=?1

? ? return?True

注：isalnum()?判斷一個字符是否為數(shù)字或者字母，lower()?字符轉(zhuǎn)小寫函數(shù)。

345. 反轉(zhuǎn)字符串中的元音字母

題目描述

編寫一個函數(shù)，以字符串作為輸入，反轉(zhuǎn)該字符串中的元音字母。

示例 1：

給定 s?=?"hello",?返回?"holle".

示例 2：

給定 s?=?"leetcode",?返回?"leotcede".

注意:

元音字母不包括?"y".

解題思路

也是采用對撞指針

代碼實現(xiàn)

class?Solution:

? def?reverseVowels(self,?s):

? ? """

? ? :type s: str

? ? :rtype: str

? ??"""

? ? ss?=?list(s)

? ? aeiou?=?['a',?'e',?'i',?'o',?'u',?'A','E','I','O','U']

? ? n?=?len(s)

? ? i?=?0

? ? j?=?n-1

? ? while?i?<?j:

? ? ? if?ss[i]?not?in?aeiou:

? ? ? ? i?+=?1

? ? ? ? continue

? ? ? if?ss[j]?not?in?aeiou:

? ? ? ? j?-=?1

? ? ? ? continue

? ? ? if?(i?<?j):

? ? ? ? ss[i],?ss[j]?=?ss[j],?ss[i]

? ? ? i?+=?1

? ? ? j?-=?1

? ? d?=?''

? ? return?d.join(ss)

11. 盛最多水的容器

題目描述

給定 n 個非負(fù)整數(shù) a1，a2，...，an，每個數(shù)代表坐標(biāo)中的一個點 (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。

圖示

解題思路

我們在由線段長度構(gòu)成的數(shù)組中使用兩個指針，一個放在開始，一個置于末尾。 此外，我們會使用變量 maxarea 來持續(xù)存儲到目前為止所獲得的最大面積。 在每一步中，我們會找出指針?biāo)赶虻膬蓷l線段形成的區(qū)域，更新 maxarea，并將指向較短線段的指針向較長線段那端移動一步。

代碼實現(xiàn)

class?Solution:

? def?maxArea(self,?height):

? ? """

? ? :type height: List[int]

? ? :rtype: int

? ??"""

? ? n?=?len(height)

? ? i?=?0

? ? j?=?n?-?1

? ? maxarea?=?(j?-?i)?*?min(height[i],?height[j])

? ? while?i?<?j:

? ? ? if?height[i]?<?height[j]:

? ? ? ? i?+=?1

? ? ? else:

? ? ? ? j?-=?1

? ? ? maxarea?=?max(maxarea,?(j?-?i)?*?min(height[i],?height[j]))

? ? return?maxarea

雙索引技術(shù)-滑動窗口

一些題目用滑動窗口方法解題，可以將時間復(fù)雜度控制在 O(n) 級別，最重要的是定義好滑動窗口，明確它要表達(dá)的意思，當(dāng)然邊界和初始值非常重要。

209. 長度最小的子數(shù)組

題目描述

給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組。如果不存在符合條件的連續(xù)子數(shù)組，返回 0。

...

解題思路

要求是連續(xù)子數(shù)組，所以我們必須定義 i，j兩個指針，i 向前遍歷，j 向后遍歷，相當(dāng)與一個滑塊，這樣所有的子數(shù)組都會在 [i...j] 中出現(xiàn)，如果 nums[i..j] 的和小于目標(biāo)值 s，那么j向后移一位，再次比較，直到大于目標(biāo)值 s 之后，i 向前移動一位，縮小數(shù)組的長度。遍歷到i到數(shù)組的最末端，就算結(jié)束了，如果不存在符合條件的就返回 0。

代碼實現(xiàn)

class?Solution:

? def?minSubArrayLen(self,?s,?nums):

? ? """

? ? :type s: int

? ? :type nums: List[int]

? ? :rtype: int

? ??"""

? ? n?=?len(nums)

? ? if?(n?<?1?or?sum(nums)?<?s):

? ? ? return?0

? ? # 維護(hù)一個滑動窗口nums[i,j], nums[i...j] < s

? ? i?=?0

? ? j?=?-1

? ? total?=?0

? ? res?=?n?+?1

? ? while?i?<=?n-1:

? ? ? if?(j?+?1?<?n)?and?total?<?s:

? ? ? ? j?+=?1

? ? ? ? total?+=?nums[j]

? ? ? else:

? ? ? ? total?-=?nums[i]

? ? ? ? i?+=?1

? ? ? if?(total?>=?s):

? ? ? ? res?=?min(res,?j-i+1)

? ? if?res?==?n+1:

? ? ? return?0

? ? return?res

總結(jié)

我們知道在準(zhǔn)備面試的時候，刷算法題是一種捷徑，特別是刷力扣，但是不能一味的刷題，我們需要總結(jié)和思考，對于一些相似的題目我們應(yīng)該多想想他們的思想，其實很多題的解題思路都是相近的。

本文作者：軍旗

編輯&版式：霍霍

聲明：本文歸 “力扣” 版權(quán)所有，如需轉(zhuǎn)載請聯(lián)系。

總結(jié)

以上是生活随笔為你收集整理的.net 遍历数组找重复值写入一个新数组_面试 | 数组类算法精析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。