????🔥個人主頁:?中草藥
🔥專欄:【算法工作坊】算法實戰揭秘
一.山脈數組的峰頂索引
題目鏈接:852.山脈數組的峰頂
?
算法原理
????????這段代碼實現了一個查找山峰數組中峰值索引的算法。山峰數組是一個先遞增后遞減的數組,即存在一個索引 i
使得對于所有的 j < i
,有 arr[j] < arr[j + 1]
,且對于所有的 k > i
,有 arr[k] > arr[k - 1]
。這個索引 i
就是峰值的索引。
????????算法使用了二分查找(Binary Search)的方法來尋找峰值索引。其核心思想是在數組中尋找拐點(即峰值),在該點左側的值小于右側的值,在右側則相反。由于數組是先升后降的,這個拐點就是我們所要找的峰值。
具體分析如下:
-
初始化兩個指針
left
和right
,分別指向數組的第二個元素和倒數第二個元素。這是因為數組的第一個和最后一個元素不可能是峰值。 -
在
while
循環中,計算中間位置mid
。這里使用(left + (right - left + 1)) / 2
而不是常見的(left + right) / 2
來避免可能的整數溢出,并確保mid
總是指向left
和right
之間的元素,包括邊界上的元素。 -
如果
arr[mid]
大于arr[mid - 1]
,說明mid
可能是峰值或者峰值在mid
的右邊,因此將left
更新為mid
。 -
否則,如果
arr[mid]
小于或等于arr[mid - 1]
,說明峰值在mid
的左邊,因此將right
更新為mid - 1
。 -
當
left
和right
相遇時,循環結束,此時left
指向的位置就是峰值的索引。
這種算法的時間復雜度是 O(log n),其中 n 是數組的長度,因為每次迭代都將搜索范圍減半。這比線性搜索的 O(n) 時間復雜度要高效得多。
代碼
public int peakIndexInMountainArray(int[] arr) {int left=1,right=arr.length-2;while(left<right){int mid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1]){left=mid;}else{right=mid-1;}}return left;}
舉例?
測試用例 arr = [0,10,5,2]
首先,初始化 left = 1
和 right = arr.length - 2 = 2
。
接下來,我們進入 while
循環:
-
第一次循環:
left = 1
,?right = 2
- 計算?
mid = left + (right - left + 1) / 2 = 1 + (2 - 1 + 1) / 2 = 2
- 檢查?
arr[mid]
?是否大于?arr[mid - 1]
,也就是檢查?arr[2]
?是否大于?arr[1]
。由于?arr[2] = 5
?并不大于?arr[1] = 10
,條件不滿足。 - 所以,我們將?
right
?更新為?mid - 1
,即?right = 1
。
-
這時,
left
和right
都指向同一個位置1
,循環條件left < right
不再滿足,循環結束。
最后,返回 left
的值,即 1
。這意味著數組中的峰值位于索引 1
上,這與給定數組 [0, 10, 5, 2]
的實際情況相吻合,因為最大值 10
確實位于索引 1
。
所以,這段代碼正確地找到了山峰數組的峰值索引。
?二.尋找峰值
題目鏈接:162.尋找峰值
?
算法原理
????????同樣使用了二分查找(Binary Search)算法來找到所謂的“峰值元素”。峰值元素定義為一個元素,它嚴格大于它的鄰居。注意,數組可以是未排序的,并且數組的兩端被認為是鄰居元素的“虛擬”較小值,這樣數組的起始元素和末尾元素也可以成為峰值元素。
算法的步驟如下:
-
初始化兩個指針
left
和right
,分別指向數組的起始位置0
和終止位置nums.length - 1
。 -
進入
while
循環,只要left
小于right
,表示搜索區間內還有多個元素需要考慮。 -
在循環內部,計算中間位置
mid
。這里使用(left + (right - left) / 2)
來避免整數溢出,并確保mid
總是落在left
和right
之間。 -
比較
nums[mid]
和nums[mid + 1]
的大小。如果nums[mid]
小于nums[mid + 1]
,那么峰值一定不在mid
及其左側,因為從mid
到mid + 1
數組是上升的。這時,將left
更新為mid + 1
。 -
否則,如果
nums[mid]
大于或等于nums[mid + 1]
,那么峰值可能在mid
或者其左側。這時,將right
更新為mid
。 -
當
left
和right
相遇時,循環結束,此時left
指向的位置就是峰值元素的索引。這是因為當left == right
時,它們共同指向的元素必定是峰值,因為在之前的迭代中,我們總是排除了較小的鄰居元素所在的那一邊。
這段代碼的時間復雜度同樣是 O(log n),其中 n 是數組的長度,因為每次迭代都將搜索范圍減半,這使得算法非常高效。
代碼
public int findPeakElement(int[] nums) {int left=0,right=nums.length-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<nums[mid+1]){left=mid+1;}else{right=mid;}}return left;}
舉例?
測試用例 [1,2,1,3,5,6,4]
我們開始分析:
-
初始化
left = 0
和right = nums.length - 1 = 6
。 -
第一次循環:
mid = left + (right - left) / 2 = 0 + (6 - 0) / 2 = 3
- 檢查?
nums[mid]
?和?nums[mid + 1]
,即?nums[3]
?和?nums[4]
,比較?3
?和?5
。 - 因為?
nums[3]
?小于?nums[4]
,所以更新?left
?為?mid + 1
,即?left = 4
。
-
第二次循環:
- 此時?
left = 4
?和?right = 6
。 mid = left + (right - left) / 2 = 4 + (6 - 4) / 2 = 5
- 檢查?
nums[mid]
?和?nums[mid + 1]
,即?nums[5]
?和?nums[6]
,比較?6
?和?4
。 - 因為?
nums[5]
?不小于?nums[6]
,所以更新?right
?為?mid
,即?right = 5
。
- 此時?
-
第三次循環:
- 現在?
left = 4
?和?right = 5
。 mid = left + (right - left) / 2 = 4 + (5 - 4) / 2 = 4
- 檢查?
nums[mid]
?和?nums[mid + 1]
,即?nums[4]
?和?nums[5]
,比較?5
?和?6
。 - 因為?
nums[4]
?小于?nums[5]
,所以更新?left
?為?mid + 1
,即?left = 5
。
- 現在?
-
第四次循環:
- 此時?
left = 5
?和?right = 5
。 - 因為?
left
?等于?right
,while
?循環的條件不再滿足,循環結束。
- 此時?
最終,函數返回 left
的值,即 5
。這表明數組 [1, 2, 1, 3, 5, 6, 4]
中的一個峰值元素位于索引 5
,其值為 6
。值得注意的是,根據題目的定義,可能有多個峰值元素,而算法保證返回的是其中一個。在這個例子中,索引 1
(nums[1] = 2
) 和索引 5
(nums[5] = 6
) 都是合法的峰值元素。
三.尋找旋轉排序數組的最小值
題目鏈接:153.尋找旋轉排序數組的最小值
??
算法原理
????????這段代碼實現了一個算法,用于在一個旋轉排序數組中找到最小元素。旋轉排序數組指的是原本有序的數組經過若干次旋轉得到的結果。例如,數組 [1, 2, 3, 4, 5]
經過旋轉可能變成 [3, 4, 5, 1, 2]
。
????????算法的原理基于二分查找(Binary Search),但是針對旋轉排序數組進行了調整。關鍵在于利用旋轉特性來縮小搜索范圍。旋轉數組的最小元素位于旋轉點之后,旋轉點之前的子數組是遞增的,旋轉點之后的子數組也是遞增的,但整個數組的順序被打亂。
算法步驟如下:
-
初始化
left
和right
分別指向數組的起始和末尾位置。 -
獲取數組最后一個元素
x
作為基準值。這是因為在旋轉數組中,最后一個元素通常是未旋轉前數組的最后一個元素,或者是旋轉后新數組的最大值。 -
進入
while
循環,只要left < right
,就說明搜索空間大于1個元素。 -
計算中間位置
mid
,使用(left + (right - left) / 2)
來避免整數溢出問題。 -
比較
nums[mid]
和x
的大小:- 如果?
nums[mid] > x
,說明?mid
?位于旋轉點的左側遞增子數組中,最小值只能在?mid
?右側的子數組中,因此更新?left
?為?mid + 1
。 - 否則,
nums[mid] <= x
,說明?mid
?位于旋轉點的右側遞增子數組中,或者正好位于旋轉點上,最小值可能在?mid
?或者左側子數組中,因此更新?right
?為?mid
。
- 如果?
-
當
left
和right
相遇時,循環結束,此時left
指向的位置就是最小元素的索引,返回nums[left]
即可得到最小值。
此算法的時間復雜度為 O(log n),其中 n 是數組的長度,因為它在每一步都有效地將搜索空間減半。這使得算法在處理大數據量時非常高效。
代碼
public int findMin(int[] nums) {int left=0,right=nums.length-1;int x=nums[right];while(left<right){int mid=left+(right-left)/2;if(nums[mid]>x){left=mid+1;}else{right=mid;}}return nums[left];}
舉例?
測試用例 nums = [4,5,6,7,0,1,2]
我們開始逐步分析:
- 初始化?
left = 0
?和?right = nums.length - 1 = 6
。 - 設置?
x = nums[right] = nums[6] = 2
。
第一次循環:
mid = left + (right - left) / 2 = 0 + (6 - 0) / 2 = 3
- 檢查?
nums[mid]
?和?x
,即?nums[3]
?和?2
,比較?7
?和?2
。 - 因為?
nums[mid]
?大于?x
,更新?left
?為?mid + 1
,即?left = 4
。
第二次循環:
- 此時?
left = 4
?和?right = 6
。 mid = left + (right - left) / 2 = 4 + (6 - 4) / 2 = 5
- 檢查?
nums[mid]
?和?x
,即?nums[5]
?和?2
,比較?1
?和?2
。 - 因為?
nums[mid]
?不大于?x
,更新?right
?為?mid
,即?right = 5
。
第三次循環:
- 此時?
left = 4
?和?right = 5
。 mid = left + (right - left) / 2 = 4 + (5 - 4) / 2 = 4
- 檢查?
nums[mid]
?和?x
,即?nums[4]
?和?2
,比較?0
?和?2
。 - 因為?
nums[mid]
?不大于?x
,更新?right
?為?mid
,即?right = 4
。
第四次循環:
- 現在?
left = 4
?和?right = 4
。 while
?循環的條件?left < right
?不再滿足,循環結束。
最終,函數返回 nums[left]
的值,即 nums[4]
,結果為 0
。
這表明數組 [4, 5, 6, 7, 0, 1, 2]
中的最小元素為 0
,位于索引 4
。此算法成功找到了旋轉排序數組中的最小元素。
四.LCR 173.點名?
題目鏈接:LCR 173.點名
?
算法原理
-
初始化兩個指針
left
和right
,分別指向數組的起始位置0
和終止位置records.length - 1
。 -
使用
while
循環,只要left < right
,意味著數組中還可能存在不匹配的情況。 -
計算中間位置
mid
,使用(left + (right - left) / 2)
來避免整數溢出。 -
檢查
mid
位置的元素是否等于mid
:- 如果?
records[mid]
?等于?mid
,這意味著?mid
?位置的值與索引匹配,因此缺失的元素可能在?mid
?的右側。更新?left
?為?mid + 1
。 - 否則,如果?
records[mid]
?不等于?mid
,這可能是由于缺失的元素在?mid
?的位置應該出現,但實際沒有出現。因此,更新?right
?為?mid
,繼續在左側查找。
- 如果?
-
當
left
和right
相遇時,循環結束。此時,left
指向的位置要么是缺失元素應該出現的位置,要么緊隨其后。 -
最后,檢查
left
位置的元素是否等于left
:- 如果?
left
?位置的元素等于?left
,這意味著?left
?位置的元素沒有缺失,因此缺失的元素應該是?left + 1
。 - 否則,
left
?位置的元素小于?left
,這意味著?left
?位置的元素是缺失的,因此缺失的元素就是?left
。
- 如果?
時間復雜度為 O(log n),其中 n 是數組的長度,因為算法使用了二分查找,每次迭代都將搜索范圍減半。
這種算法特別適用于數據量大、有序或部分有序的數組中查找缺失的元素,效率遠高于線性查找。
代碼
public int takeAttendance(int[] records) {int left=0,right=records.length-1;while(left<right){int mid=left+(right-left)/2;if(mid==records[mid]){left=mid+1;}else{right=mid;}}//判斷特殊情況,如[0,1,2,3,4,5]此時缺少的值應該是6if(left==records[left]){return left+1;}return left;}
舉例?
測試用例 records = [0, 1, 2, 3, 4, 5, 6, 8]
我們開始逐步分析:
- 初始化?
left = 0
?和?right = records.length - 1 = 7
。
第一次循環:
mid = left + (right - left) / 2 = 0 + (7 - 0) / 2 = 3
- 檢查?
records[mid]
?和?mid
,即?records[3]
?和?3
,比較?3
?和?3
。 - 因為?
records[mid]
?等于?mid
,更新?left
?為?mid + 1
,即?left = 4
。
第二次循環:
- 此時?
left = 4
?和?right = 7
。 mid = left + (right - left) / 2 = 4 + (7 - 4) / 2 = 5
- 檢查?
records[mid]
?和?mid
,即?records[5]
?和?5
,比較?5
?和?5
。 - 因為?
records[mid]
?等于?mid
,更新?left
?為?mid + 1
,即?left = 6
。
第三次循環:
- 此時?
left = 6
?和?right = 7
。 mid = left + (right - left) / 2 = 6 + (7 - 6) / 2 = 6
- 檢查?
records[mid]
?和?mid
,即?records[6]
?和?6
,比較?6
?和?6
。 - 因為?
records[mid]
?等于?mid
,更新?left
?為?mid + 1
,即?left = 7
。
第四次循環:
- 現在?
left = 7
?和?right = 7
。 while
?循環的條件?left < right
?不再滿足,循環結束。
退出循環后:
- 檢查?
left
?位置的元素是否等于?left
,即?records[7]
?和?7
,比較?8
?和?7
。 - 因為?
records[left]
?不等于?left
,直接返回?left
?的值,即?7
。
然而,根據代碼邏輯,如果 left
位置的元素等于 left
,我們應該返回 left + 1
;否則,返回 left
。在本例中,left
已經等于數組的長度,且 records[left]
實際上超出了正常的序列,因此正確結果應為 left
的值,即 7
,這表明缺失的元素是 7
。
因此,這段代碼正確地找到了測試用例 [0, 1, 2, 3, 4, 5, 6, 8]
中缺失的元素,即 7
。
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
以上,就是本期的全部內容啦,若有錯誤疏忽希望各位大佬及時指出💐
? 制作不易,希望能對各位提供微小的幫助,可否留下你免費的贊呢🌸