此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.
想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!
文章目錄
- 0.導圖整理
- 1.常規思想的改進: 假合并/奇偶合并
- 2.尋找第k小數 代碼詳解
- 3.理解中位數作用進行 劃分陣列
- 原始碼
- Python:
- java:
題目鏈接: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
力扣上對于此題的各種思想的講解已經非常詳細了(圖文并茂), 但是他們對于自己的代碼幾乎沒什么補充, 大多都是思想講解完成直接就上代碼了, 但是本題即使思想理解了, 在代碼的理解上還是有難度的, 所以本文重點對 代碼的理解 做了詳細的解釋.
0.導圖整理
1.常規思想的改進: 假合并/奇偶合并
本題的常規思想還是挺簡單的: 使用歸并的方式, 合并兩個有序陣列, 得到一個大的有序陣列. 大的有序陣列的中間位置的元素, 即為中位數. 但是這種思路的時間復雜度是 O(m+n), 空間復雜度是 O(m+n), 面試的時候, 面試官肯定不會滿意這樣的答案的.
因此我們必須想辦法將演算法進行優化, 這里先介紹一種簡單的優化方式, 就是 假合并, 即我們并不需要真的合并兩個有序陣列, 只要找到中位數的位置即可.
它的思想并不復雜, 由于兩個陣列的長度已知, 因此中位數對應的兩個陣列的下標之和也是已知的，維護兩個指標, 初始時分別指向兩個陣列的下標0的位置, 每次將指向較小值的指標后移一位（如果一個指標已經到達陣列末尾,則只需要移動另一個陣列的指標）, 直到到達中位數的位置.
通過這種 假合并 的方式, 我們可以成功的將空間復雜度優化到了O(1), 但是對于時間復雜度并沒有什么優化. 講解這個方法的目的并不是為了讓大家掌握此方法, 而是為了讓大家掌握此方法的一些巧妙的 優化方式.
此方法理解是比較容易的, 但是真正寫代碼時候還是很有挑戰的, 你不僅要考慮奇偶的問題, 更要考慮 一個陣列遍歷結束后 的各種邊界問題, 其實很多困難題就是難在了對于邊界的處理上面了.
此方法的一個優化點就是 將奇偶兩種情況合并到了一起, 具體思想如下:
這種思想是很有必要的, 對于陣列來說, 我們經常會遇到奇偶的兩種情況處理, 如果想辦法將他們合并在一起, 那代碼寫起來就是非常順暢和整潔.
另一種合并的思想是: 我們可以在奇數的時候, 在末尾等處添加一個占位符#等, 這樣也是可以將奇數合并成偶數的情況的.
此方法的另一個優化點就是 通過在if條件中加入大量的限制條件, 從而實作了對于各種邊界問題的處理, 這也是一種很重要的思想.
此方法的時間復雜度相對于下面兩種思想還是太高了, 大家不用特意掌握此方法, 但是這兩個優化的思想還是很重要的, 要好好的理解一下.
接下來我們就來詳細講解兩個時間復雜度超低的演算法代碼思想.
2.尋找第k小數 代碼詳解
關于本題轉換為 第k小數 的思想, 就不用糾結怎么想到的了, 大家就安心的理解思想和代碼并將它記在腦中就可以了.
其實關于這個演算法的思想并不是太難理解, 主要就是根據兩個數的三種比較結果, 不斷地去除不滿足的元素的程序.
我認為這個思想最難的點在于 三種特殊情況的處理, 我們能否想到這三種情況, 并將他們完美的融入到代碼之中, 我感覺這才是真正的難點所在.
接下來我們來詳細解讀此思想的代碼實作.
最開始對于奇數和偶數的兩種情況進行了判斷, 其實是可以將兩種情況合并的, 只需要在奇數時求兩次同樣的k就可以了.
接下來處理了三種特殊情況中的兩種特殊情況: 一個陣列為空 和 k=1.
下面的幾個定義就非常重要了, 一定要弄清這些定義的含義, 才能更輕松的理解代碼.
index1, index2作為陣列的起始點的下標, 初值都是0, 但是隨著兩個陣列不斷被洗掉元素, 這兩個起始點也是在不斷的進行變化, 具體變化方式就是 index1 = newIndex1 + 1, 因為在洗掉元素的時候 連同比較位置也一同刪去了, 所以新的開始是 比較位置 的后一位.
newindex1, newindex2作為比較點就是圖中被框中的兩個數的下標, 它的賦值程序就涉及到了 最后一個邊界情況. 因為當一個陣列較短時, 其中一個比較點可能已經到達了陣列的最后, 所以它的值是 兩種情況下較小的那個數.
接下來就是根據兩個比較點的大小來進行不同的操作程序了, 這里最難理解的點就是 k -= (newIndex1 - index1 + 1), 也就是減去元素的個數問題了. 我們根據上面的圖來舉例, 圖中index1的值為0, newindex1的值經過計算為1, 通過比較后, 可以看到 紅色的數 就是被洗掉的數, 也就是兩個, 所以我們需要在最后+1才是真實被刪去的個數. 對于此類問題在確定最終個數的時候, 我們都可以通過這樣的特例來決定代碼的書寫, 至此代碼就全部講解完成了.
3.理解中位數作用進行 劃分陣列
最后這種思想的時間復雜度甚至比上面的還低, 上面的思想每一輪回圈可以將查找范圍減少一半,因此時間復雜度是O(log(m+n)), 但這種思想可以對確定的較短的陣列進行二分查找, 所以它的時間復雜度是 O(log min(m,n)).
劃分陣列 正好和上面演算法完全相反, 它的思想特別復雜, 但思想理解了, 代碼寫起來倒是沒太大的難度, 所以我們重點說說它的思想.
首先我們要明白中位數的作用: 將一個集合劃分為兩個長度相等的子集, 其中一個子集中的元素總是大于另一個子集中的元素, 這種思想無論是在幾個陣列中都是適用的, 這就衍生出了下面的演算法思想.
首先來討論奇偶的兩種不同情況下的不同劃分方式.
然后在撰寫代碼的時候, 由于計算機的取整操作, 我們是可以將這兩種情況合并成一種代碼書寫方式的. 其中的i和j分別是兩個陣列的劃分位置.
同樣我們也會遇到復雜的邊界問題, 但下面這種處理方式是真的非常優秀.
上面問題都考慮完了, 其實就可以寫代碼了, 但是我們需要進行兩個條件的判斷: B[j?1]≤A[i] 以及A[i?1]≤B[j], 為了優化代碼, 經過分析后, 我們發現這兩種情況是可以等價轉換的. 也就是只需要進行一個條件的判斷即可.
代碼中有個注意點就是java中的三目運算子? : 在Python中是沒有引入這個符號的, 但是Python利用了已有的關鍵字if…else實作了這個功能.
原始碼
Python:
# 常規思想
class Solution:
def findMedianSortedArrays(self, A: List[int], B: List[int]) -> float:
m = len(A)
n = len(B)
lens = m + n
left, right = -1, -1
aStart, bStart = 0, 0
for i in range(lens//2 + 1) :
left = right # 每次回圈前將 right 的值賦給 left
# A移動的條件: B遍歷到最后 或 當前A<B,滿足一個即可
if aStart < m and (bStart >= n or A[aStart] < B[bStart]):
right = A[aStart]
aStart += 1
else :
right = B[bStart]
bStart += 1
if (lens & 1) == 0: # 與1交,判斷奇偶數,更快速
return (left + right) / 2.0
else:
return right
# 第k小數
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def getKthElement(k):
"""
- 主要思路：要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較
- 這里的 "/" 表示整除
- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個
- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個
- 取 pivot = min(pivot1, pivot2),兩個陣列中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個
- 這樣 pivot 本身最大也只能是第 k-1 小的元素
- 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素，把這些元素全部 "洗掉",剩下的作為新的 nums1 陣列
- 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素，把這些元素全部 "洗掉",剩下的作為新的 nums2 陣列
- 由于我們 "洗掉" 了一些元素（這些元素都比第 k 小的元素要小）,因此需要修改 k 的值,減去洗掉的數的個數
"""
index1, index2 = 0, 0
while True:
# 特殊情況
if index1 == m:
return nums2[index2 + k - 1]
if index2 == n:
return nums1[index1 + k - 1]
if k == 1:
return min(nums1[index1], nums2[index2])
# 正常情況,index1,index2作為起始點,newindex1,newindex2作為比較點 在不停的更新
newIndex1 = min(index1 + k // 2 - 1, m - 1) # 第一種特殊情況,發生越界,記錄需要比較的位置
newIndex2 = min(index2 + k // 2 - 1, n - 1) # 第一種特殊情況,發生越界,記錄需要比較的位置
pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2] # 獲取兩個需要比較的數
if pivot1 <= pivot2: # <=將兩種情況合并
k -= newIndex1 - index1 + 1 # 兩者相減后+1,這才是真正減去的長度
index1 = newIndex1 + 1 # 連同比較位置也一同刪去了,所以新的開始是 比較位置 的后一位
else:
k -= newIndex2 - index2 + 1
index2 = newIndex2 + 1
m, n = len(nums1), len(nums2)
totalLength = m + n
if totalLength % 2 == 1: # 可以將兩種情況合并,奇數會求兩次同樣的k
return getKthElement((totalLength + 1) // 2)
else:
return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2
# 劃分陣列
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
return self.findMedianSortedArrays(nums2, nums1)
infinty = 2**40 # 代表正無窮
m, n = len(nums1), len(nums2)
left, right = 0, m
# median1：前一部分的最大值
# median2：后一部分的最小值
median1, median2 = 0, 0
while left <= right: # 一直回圈找到一個最大的i滿足A[i?1]≤B[j]
# 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
# // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
i = (left + right) // 2
j = (m + n + 1) // 2 - i
# nums_im1, nums_i, nums_jm1, nums_j 分別表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
# 當一個陣列不出現在前一部分時,對應的值為負無窮,就不會對前一部分的最大值產生影響
nums_im1 = (-infinty if i == 0 else nums1[i - 1]) # 注意寫法與java不同
# 當一個陣列不出現在后一部分時,對應的值為正無窮,就不會對后一部分的最小值產生影響
nums_i = (infinty if i == m else nums1[i])
nums_jm1 = (-infinty if j == 0 else nums2[j - 1])
nums_j = (infinty if j == n else nums2[j])
if nums_im1 <= nums_j:
median1, median2 = max(nums_im1, nums_jm1), min(nums_i, nums_j)
left = i + 1
else:
right = i - 1
return (median1 + median2) / 2 if (m + n) % 2 == 0 else median1
java:
// 常規思想
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
int len = m + n;
int left = -1, right = -1;
int aStart = 0, bStart = 0;
for (int i = 0; i <= len / 2; i++) {
left = right; // 每次回圈前將 right 的值賦給 left
// A移動的條件: B遍歷到最后 或 當前A<B,滿足一個即可
if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
right = A[aStart++];
} else {
right = B[bStart++];
}
}
if ((len & 1) == 0) // 與1交,判斷奇偶數,更快速
return (left + right) / 2.0;
else
return right;
}
}
// 第k小數
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length;
int totalLength = length1 + length2;
if (totalLength % 2 == 1) { // 可以將兩種情況合并,奇數會求兩次同樣的k
int midIndex = totalLength / 2;
double median = getKthElement(nums1, nums2, midIndex + 1);
return median;
} else {
int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
return median;
}
}
public int getKthElement(int[] nums1, int[] nums2, int k) {
/* 主要思路：要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較
* 這里的 "/" 表示整除
* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個
* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個
* 取 pivot = min(pivot1, pivot2),兩個陣列中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個
* 這樣 pivot 本身最大也只能是第k-1小的元素
* 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素，把這些元素全部 "洗掉",剩下的作為新的 nums1 陣列
* 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素，把這些元素全部 "洗掉",剩下的作為新的 nums2 陣列
* 由于我們 "洗掉" 了一些元素（這些元素都比第 k 小的元素要小）,因此需要修改 k 的值,減去洗掉的數的個數
*/
int length1 = nums1.length, length2 = nums2.length;
int index1 = 0, index2 = 0;
int kthElement = 0;
while (true) {
// 特殊情況
if (index1 == length1) { // 第二種特殊情況,一個陣列為空
return nums2[index2 + k - 1];
}
if (index2 == length2) { // 第二種特殊情況,一個陣列為空
return nums1[index1 + k - 1];
}
if (k == 1) { // 第三種特殊情況,k=1
return Math.min(nums1[index1], nums2[index2]);
}
// 正常情況,index1,index2作為起始點,newindex1,newindex2作為比較點 在不停的更新
int half = k / 2;
int newIndex1 = Math.min(index1 + half, length1) - 1; //第一種特殊情況,發生越界,記錄需要比較的位置
int newIndex2 = Math.min(index2 + half, length2) - 1; //第一種特殊情況,發生越界,記錄需要比較的位置
int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]; //獲取兩個需要比較的數
if (pivot1 <= pivot2) { // <=將兩種情況合并
k -= (newIndex1 - index1 + 1); //兩者相減后+1,這才是真正減去的長度
index1 = newIndex1 + 1; //連同比較位置也一同刪去了,所以新的開始是 比較位置 的后一位
} else {
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1;
}
}
}
}
// 劃分陣列
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int left = 0, right = m;
// median1：前一部分的最大值
// median2：后一部分的最小值
int median1 = 0, median2 = 0;
while (left <= right) { // 一直回圈找到一個最大的i滿足A[i-1]≤B[j]
// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
int i = (left + right) / 2; //二分法,i從區間中間開始
int j = (m + n + 1) / 2 - i;//+1的操作將總數為奇數和偶數合并為一種情況
//nums_im1, nums_i, nums_jm1, nums_j 分別表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
//當一個陣列不出現在前一部分時,對應的值為負無窮,就不會對前一部分的最大值產生影響
int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
//當一個陣列不出現在后一部分時,對應的值為正無窮,就不會對后一部分的最小值產生影響
int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);
if (nums_im1 <= nums_j) {
median1 = Math.max(nums_im1, nums_jm1);
median2 = Math.min(nums_i, nums_j);
left = i + 1;
}
else {
right = i - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
}
}
我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)
最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目
最值得收藏的 計算機網路 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介
最值得收藏的 演算法分析與設計 全部知識點思維導圖整理(北大慕課課程)
最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理
最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)
最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)
最值得收藏的 數字影像處理 全部知識點思維導圖整理(武漢大學慕課課程)
紅黑樹 一張導圖解決紅黑樹全部插入和洗掉問題 包含詳細操作原理 情況對比
各種常見排序演算法的時間/空間復雜度 是否穩定 演算法選取的情況 改進 思維導圖整理
人工智能課件 演算法分析課件 Python課件 數值分析課件 機器學習課件 影像處理課件
考研相關科目 知識點 思維導圖整理
考研經驗–東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)
東南大學 軟體工程 906 資料結構 C++ 歷年真題 思維導圖整理
東南大學 軟體工程 復試3門科目歷年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
高等數學 中值定理 一張思維導圖解決中值定理所有題型
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm框架全部筆記
Spring springmvc Mybatis jsp
科技相關 小米手機
小米 紅米 歷代手機型號大全 發布時間 發布價格
常見手機品牌的各種系列劃分及其特點
歷代CPU和GPU的性能情況和常見后綴的含義 思維導圖整理
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/298939.html
標籤：java
上一篇：重戰資料結構與演算法：沖刺大廠----＞＞稀疏陣列與佇列
下一篇：Java學習筆記：高階語法