資訊專欄INFORMATION COLUMN
摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷算法題目的順序/注意點/技巧, 以及思維導圖源文件問題請點擊此鏈接.
想進大廠, 刷算法是必不可少的, 歡迎和博主一起打卡刷力扣算法! 博主同步更新了算法視頻講解, 更易于理解, 不想看文章的 歡迎來看!
關注博主獲得題解更新的最新消息!!!
這是最容易想到的方法: 先將數組nums2放進數組nums1的尾部, 然后直接對整個數組進行排序. 實現起來也是非常簡單的, 但時間復雜度和空間復雜度都很高, 畢竟用到了排序算法, 建議面試時候千萬別寫這種題解, 不然可能直接就回去等通知了!
方法一沒有利用數組nums1與nums2已經被排序的性質, 為了利用這一性質, 可以使用雙指針方法, 將兩個數組看作隊列, 每次從兩個數組頭部取出比較小的數字放到結果中, 這時有個注意點: 必須當兩個數組的指針都到達尾部時, 算法才算結束, 這點和下面的方法還是有點區別的, 需要注意一下.
最后一個小的注意點就是在python中的語法: nums1[:] = sorted, 它表示對nums1從頭到尾切片, 然后進行一一賦值, 相當于進行了深拷貝.
方法二中, 之所以要使用臨時數組變量, 是因為如果直接合并到數組nums1中, nums1中的元素可能會在取出之前被覆蓋.
觀察可知, nums1的后半部分是空的, 可以直接覆蓋而不會影響結果, 所以可以將指針設置為從后向前遍歷, 每次取兩者之中的較大者放進nums1的最后面, 這樣就完美的解決了被覆蓋的問題. 下面是合理性的證明, 感興趣的可以看一下.
嚴格來說，在此遍歷過程中的任意一個時刻，nums1數組中有m?p1?1個元素被放入nums1的后半部，nums2數組中有n?p2?1個元素被放入nums1的后半部，而在指針p1的后面，nums1數組有m+n?p1?1個位置。由于m+n?p1 ?1≥m?p1 ?1+n?p2 ?1 等價于 p2≥?1永遠成立，因此p1后面的位置永遠足夠容納被插入的元素，不會產生p1的元素被覆蓋的情況最后有個注意點, 之前我們說到方法二終止的條件是: 兩個指針都遍歷到了數組結尾, 但是在這種方法中, 并不需要兩個指針都遍歷到開頭, 只需要nums2空了, 遍歷就結束了, 不用考慮nums1, 因為此時nums1中剩下的元素都是小于nums2的最小元素的, 且它們的順序本來就是排好的, 所以在代碼上相較于方法二有了一些簡化的操作. 具體可以看兩者代碼的不同.
這是在面試中可能會被問到的進階問題, 解決的方法是: 在方法三的基礎上, 因為是有序的, 每次比較完兩個值后判斷前一個放進數組里的值是不是和這次將要放進數組的值相等就行了, 如果相等的話這一步比較出來的值就不放進數組.
但其實這樣還是有點問題的: 如果是從大往小排, 如果邊排邊丟, 可能最后排好的部分全在nums1的后面, 仍然需要遍歷一次, 把所有數挪回左邊. 如果排完再丟, 也是遍歷一次, 感覺沒啥區別.
所以這兩種方式, 先排再丟 和 邊排邊丟 似乎是沒有區別的, 大家可以自己思考一下, 有問題歡迎留言評論.
# 直接合并后排序class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: nums1[m:] = nums2 nums1.sort()# 常規雙指針class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: sorted = [] p1, p2 = 0, 0 while p1 < m or p2 < n: # 同時到達尾部才結束 if p1 == m: sorted.append(nums2[p2]) p2 += 1 elif p2 == n: sorted.append(nums1[p1]) p1 += 1 elif nums1[p1] < nums2[p2]: sorted.append(nums1[p1]) p1 += 1 else: sorted.append(nums2[p2]) p2 += 1 nums1[:] = sorted # 對nums1從頭到尾切片, 相當于進行了深拷貝# 逆向雙指針class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: p1, p2 = m - 1, n - 1 tail = len(nums1) - 1 while p2 >= 0: if p1 < 0 or nums1[p1] <= nums2[p2]: nums1[tail] = nums2[p2] p2 -= 1 tail -= 1 else: nums1[tail] = nums1[p1] p1 -= 1 tail -= 1// 直接合并后排序class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { for (int i = 0; i != n; ++i) { nums1[m + i] = nums2[i]; } Arrays.sort(nums1); }}// 常規雙指針class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = 0, p2 = 0; int[] sorted = new int[m + n]; int cur; while (p1 < m || p2 < n) { // 同時到達尾部才結束 if (p1 == m) { cur = nums2[p2++]; } else if (p2 == n) { cur = nums1[p1++]; } else if (nums1[p1] < nums2[p2]) { cur = nums1[p1++]; } else { cur = nums2[p2++]; } sorted[p1 + p2 - 1] = cur; } for (int i = 0; i != m + n; ++i) { nums1[i] = sorted[i]; } }}// 逆向雙指針class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int tail = nums1.length - 1; int p1 = m - 1; int p2 = n - 1; while (p2 >= 0) { // 只要p2到達開頭就結束 if (p1 < 0 || nums1[p1] <= nums2[p2]) { nums1[tail--] = nums2[p2--]; } else { nums1[tail--] = nums1[p1--]; } } }}我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟件/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣算法刷題 根據思維導圖整理筆記快速記憶算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/數據結構/常見錯誤/經典思想(持續更新中)
最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟件工程初試906科目
最值得收藏的 計算機網絡 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介
最值得收藏的 算法分析與設計 全部知識點思維導圖整理(北大慕課課程)
最值得收藏的 數據結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理
最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)
最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)
最值得收藏的 數字圖像處理 全部知識點思維導圖整理(武漢大學慕課課程)
紅黑樹 一張導圖解決紅黑樹全部插入和刪除問題 包含詳細操作原理 情況對比
各種常見排序算法的時間/空間復雜度 是否穩定 算法選取的情況 改進 思維導圖整理
人工智能課件 算法分析課件 Python課件 數值分析課件 機器學習課件 圖像處理課件
考研相關科目 知識點 思維導圖整理
考研經驗–東南大學軟件學院軟件工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)
東南大學 軟件工程 906 數據結構 C++ 歷年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm框架全部筆記
科技相關 小米手機
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/123624.html
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
閱讀 825·2021-11-22 11:59
閱讀 3230·2021-11-17 09:33
閱讀 2307·2021-09-29 09:34
閱讀 1940·2021-09-22 15:25
閱讀 1954·2019-08-30 15:55
閱讀 1320·2019-08-30 15:55
閱讀 529·2019-08-30 15:53
閱讀 3345·2019-08-29 13:55
