【Leetcode】python – [88] Merge Sorted Array 個人解法筆記 | 內含 python while-else 用法說明 (updated: 2022/5/11)

➣ Reading Time: 14 minutes

題目出處

88. Merge Sorted Array

難度

Easy

題目分類

array, two-pointers

個人範例程式碼 – 2022/5/11

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        m, n = m-1, n-1 # get last idx
        for idx in range(len(nums1)-1, -1, -1):
            if(m >= 0 and n >= 0):
                if nums1[m] < nums2[n]:
                    nums1[idx] = nums2[n] 
                    n -= 1
                else:
                    nums1[idx] = nums1[m] 
                    m -= 1
            elif m >= 0:
                nums1[idx] = nums1[m] 
                m -= 1   
            elif n >= 0:
                nums1[idx] = nums2[n] 
                n -= 1

最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解

算法說明

從尾巴開始往前填,注意一下順序即可

input handling

在 for 迴圈中一起處理

Boundary conditions

for 迴圈控制範圍

個人範例程式碼 – 2022/2/25

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        while (m > 0 and n > 0): 
            if(nums1[m-1] >= nums2[n-1]):
                nums1[m+n-1] = nums1[m-1] # put nums1[m] in to the last place of nums1
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        else:
            while n > 0: # m = 0
                nums1[m+n-1] = nums2[n-1]
                n -= 1
            # else m > 0, already in nums1

說明

這題我們可以先注意題目的敘述:
最需要思考的部分在於「題目希望最後的結果直接儲存在 nums1 裡面

雖然這樣的限制會使我們解題更加的「受到限制」,但反過來說,
其實這也是題目給我們「最大的提示」。

題目的 nums1 給的空間為 m+n,所以最後我們都會將所有的值擺入 nums1 中,
而因為我們可以無憂慮去更改的值為最後的 0,0,0… 部分
(因為這個值就算被改消失了,也不影響我們想計算的結果)

所以這邊可以推斷出一定要「從後面開始解」,「從最無痛的 0 開始取代」,

再來我們就可以來思考,什麼時候擺入 nums1的值? 什麼時候擺入 nums2 的值?
我們可以靠著題目所給的 m, n 來進行這樣的操作,透過值不斷擺入,
我們去移動 m, n 作為 index 的座標,即可順利完成此題目。

邊際情況處理

這題要注意的邊際情況為 m=0, n=0 的時候我們要怎麼處理,
而照題目的敘述,

  • n=0 基本上對我們來說沒差,因為 m 控制的 nums1 即代表我們要的答案
  • m=0 才是重點,如果還有剩餘的 n,都需要擺入 nums1 中,而位置索幸很好取得,
    依然可以透過 m+n-1 算出

注意 index 細節,才是這題要考細心的部分

這題有很多 index 細節考驗著作答者的細心度,
包含:

  • 迴圈的範圍僅限於 m, n > 0 時,其他需要進例外處理
  • m-1, n-1 才是當下座標
  • 要擺入的位置為 m+n-1
  • 處理到 n > 0 就應該停下,而非 n >= 0

python while-else 用法說明

一般來說,我們通常都只會使用到 while,
但其實在 python 中,while 是可以搭配 else 使用的。

邏輯如下:

while(條件成立):
    # 成立時循環
else: # 當不成立時,出現在這
    # 當條件不成立時,開始作這邊的事情

這個寫法,可能很多人覺得好像有沒有 else 似乎不會有太大的影響?
畢竟當 while 條件不成立後,後續的程式碼「本來就會執行

沒有錯!!!! 但是這個小細節,卻可以讓我們的程式碼邏輯更漂亮!

例如說當我們有無關 while 的相關內容,我們才應該擺在外面,
但有時候是剛結束迴圈時有一些收尾的相關內容要處理,這時候用 else 的寫法就相當漂亮了!

範例

假設我們要把一個 mylist 「純手動」印成 [1,2,3] 的樣子,
最後還要印出一個 finish!

mylist = [1,2,3]
idx = 0
print('[', end = '')
while(idx < len(mylist)):
    print(mylist[idx], ',')
    idx += 1
else:
    print(']')
print('finish!')

這個例子應該就很好懂了,我們集中「把要處理 list 列印的動作」放在 while-else 裡面,
最後比較無關的 finish! 放在 while-else 外面,
這樣看起來程式碼邏輯有沒有比都放在外面更清楚了呢? (當然,見仁見智啦XDDD,我覺得有XD)

特殊用法 – while-else 搭配 break 使用的情況

這也是我近期解題才發現的,當 while – else 搭配 break 使用時,能發揮更好閱讀的效果!

請讀者先想像一下,下面的程式碼會印出什麼呢?

while(True):
    break
else:
    print(1)
print(2)

答案不是 1 2 !!! 而是只有 2 !!!

這樣我們就能夠更進階的使用這個功能了,

  • 「透過 while 迴圈條件結束的,寫在 else 裡面」
  • 「如果是透過 break 結束的,寫在最外面」

使用方式可以看我下面這題的示範:

【Leetcode】python – [142] Linked List Cycle II 個人解法筆記 | 內含 python while-else 用法介紹

Reference

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word LadderBFS (分層), DFSGraphPython
[Lint] 127Topological SortingBFS (拓撲)Python
內有 indegree, outdegree 介紹 #重要題型
207Course ScheduleBFS (拓樸)GraphPython
210Course Schedule IIBFS (拓樸)GraphPython
[Lint] 892Alien DictionaryBFS (拓樸)GraphPython
[Lint] 431Connected Component in Undirected GraphBFS (連通塊)GraphPython 內含 BFS 模板 #重要題型
1091Shortest Path in Binary MatrixBFS (最短路徑)MatrixPython
⭐ Binary Serach 相關題型 ⭐
33Search in Rotated Sorted ArrayBinary SerachArrayPython #重要題型
34Find First and Last Position of Element in Sorted ArrayBinary SerachPython
50Pow(x, n) Binary SerachPython
153Find Minimum in Rotated Sorted Array Binary SerachArrayPython
162Find Peak ElementBinary SerachPython
278First Bad VersionBinary SerachPython
658Find K Closest ElementsBinary SerachPython
704Binary SearchBinary SerachPython
852Peak Index in a Mountain ArrayBinary SerachPython
[Lint] 14First Position of TargetBinary SerachPython
[Lint] 140Fast PowerBinary SerachPython
[Lint] 447Search in a Big Sorted ArrayBinary SerachArrayPython
[Lint] 458Last Position of TargetBinary SerachPython
191Number of 1 BitsBit ManipulationPython
⭐ Data Stream 相關題型 ⭐
[Lint] 642Moving Average from Data StreamData StreamQueuePython
⭐ Design 相關題型 ⭐
155Min StackDesignPython
[Lint] 659Encode and Decode StringsDesignPython
232Implement Queue using StacksDesignQueue, StackPython
⭐ DFS 相關題型 ⭐
98Validate Binary Search TreeDFSPython
2265Count Nodes Equal to Average of SubtreeDFSPython
292nd Weekly Contest
2261K Divisible Elements SubarraysDFSPython
內含 python substring 常見作法 / 291st LeetCode Weekly Contest
22Generate ParenthesesDFSPython
79Word SearchDFSMatrixPython
126Word Ladder IIDFSPython
212Word Search IIDFSTreePython
290Word PatternDFSPython
[Lint] 829Word Pattern IIDFSPython
31Next PermutationDFS (排列)Python
46PermutationsDFS (排列)Python
#重要題型
47Permutations IIDFS (排列)Python
#重要題型
51N-QueensDFS (排列)Python
52N-Queens IIDFS (排列)Python
[Lint] 862Next Closest TimeDFS (排列)Python
內有 set 判斷是否 subset 的用法
10Regular Expression MatchingDFS (組合)Python
77CombinationsDFS (組合)Python
#重要題型
39Combination SumDFS (組合)Python
40Combination Sum IIDFS (組合)Python
216Combination Sum IIIDFS (組合)Python
377Combination Sum IVDFS (組合)Python
44Wildcard MatchingDFS (組合)Python
78SubsetsDFS (組合)Python
#重要題型
90Subsets IIDFS (組合)Python
#重要題型
131Palindrome PartitioningDFS (組合)Python
139Word BreakDFS (組合)Python
140Word Break IIDFS (組合)Python
[Lint] 90k Sum IIDFS (組合)Python
[Lint] 680Split StringDFS (組合)Python
173Binary Search Tree IteratorDFS (BST)BSTPython
#重要題型
230Kth Smallest Element in a BSTDFS (BST)BSTPython
[Lint] 448Inorder Successor in BSTDFS (BST)BSTPython
[Lint] 900Closest Binary Search Tree ValueDFS (BST)BSTPython
[Lint] 901Closest Binary Search Tree Value IIDFS (BST)BSTPython
#綜合難題
208Implement Trie (Prefix Tree)DFS (Graph)TreePython
17Letter Combinations of a Phone NumberDFS (Graph)GraphPython
332Reconstruct ItineraryDFS (Graph)GraphPython
#重要題型
110Balanced Binary TreeDFS (Tree)TreePython
226Invert Binary TreeDFS (Tree)TreePython
572Subtree of Another TreeDFS (Tree)TreePython
105Construct Binary Tree from Preorder and Inorder TraversalDFS (Tree)TreePython
112Path SumDFS (Tree)Python
113Path Sum IIDFS (Tree)TreePython
235Lowest Common Ancestor of a Binary Search TreeDFS (Tree)TreePython
236Lowest Common Ancestor of a Binary TreeDFS (Tree)TreePython
#重要題型
257Binary Tree PathsDFS (Tree)TreePython
[Lint] 474Lowest Common Ancestor IIDFS (Tree)TreePython
[Lint] 578Lowest Common Ancestor IIIDFS (Tree)TreePython
[Lint] 596Minimum SubtreeDFS (Tree)TreePython
543Diameter of Binary TreeDFS (Tree)Python
144Binary Tree Preorder TraversalDFS (Tree)TreePython
內含 處理 Tree 樹問題的重點
145Binary Tree Postorder TraversalDFS (Tree)TreePython
114Flatten Binary Tree to Linked ListDFS (Tree)TreePython
⭐ Dynamic Programming 相關題型 ⭐
338Counting BitsDPPython
309Best Time to Buy and Sell Stock with CooldownDPPython
2266Count Number of TextsDPPython
292nd Weekly Contest
2262Total Appeal of A StringDPPython
291st Weekly Contest
91Decode Ways DPPython C++
70Climbing Stairs DPPython C++
221Maximal SquareDPPython
53Maximum SubarrayDP (一維)ArrayPython C++ 內含 C++ vector max 用法整理
91Decode WaysDP (一維)Python
55Jump GameDP (一維)Python
#重要題型
45Jump Game IIDP (一維)Python
#重要題型
198House RobberDP (一維)Python
213House Robber IIDP (一維)Python
509Fibonacci NumberDP (一維)Python
122Best Time to Buy and Sell Stock IIDP (一維)Python
300Longest Increasing SubsequenceDP (一維接龍, LIS)Python
#重要題型
62Unique PathsDP (二維)Python C++
63Unique Paths IIDP (二維)Python C++
152Maximum Product SubarrayDP (二維)Python
#重要題型
118Pascal’s TriangleDP (二維)Python
內含 python sum of two list (list add 相加方法整理)
322Coin ChangeDP (背包問題)Python
內含 DP 背包問題模板 #重要題型
518Coin Change 2DP (背包問題)Python
#重要題型
[Lint] 92BackpackDP (背包問題)Python
[Lint] 125Backpack IIDP (背包問題)Python
[Lint] 440Backpack IIIDP (背包問題)Python
[Lint] 562Backpack IVDP (背包問題)Python
[Lint] 563Backpack VDP (背包問題)Python
[Lint] 798Backpack VIIDP (背包問題)Python
[Lint] 799Backpack VIIIDP (背包問題)Python
[Lint] 800Backpack IXDP (背包問題)Python
[Lint] 801Backpack XDP (背包問題)Python
1143Longest Common SubsequenceDP (LCS)Python
494Target SumDP (Memoization)Python
2267Check if There Is a Valid Parentheses String PathDP (Memoization)Python
內含:Memoization 記憶化搜索筆記 / 292nd Weekly Contest
⭐ Hash 相關題型 ⭐
13Roman to IntegerHashPython
73Set Matrix Zeroes HashPython C++ 內含 python while-else 用法說明
692Top K Frequent WordsHashPython
內含 python 自定義排序 key function 的使用方法
846Hand of StraightsHashPython
347Top K Frequent ElementsHashPython
205Isomorphic StringsHashPython
268Missing NumberHashPython
242Valid AnagramHashPython
763Partition LabelsHashIntervalPython
383Ransom NoteHashPython
387 First Unique Character in a String HashPython
2186Minimum Number of Steps to Make Two Strings Anagram IIHashPython
282nd Weekly Contest
[Lint] 793Intersection of ArraysHashPython
146LRU CacheHashPython
387First Unique Character in a StringHashPython
[Lint] 920Meeting RoomsHashIntervalPython
#重要題型
[Lint] 920Meeting RoomsHashIntervalPython
#重要題型
[Lint] 919Meeting Rooms IIHashIntervalPython
#重要題型
[Lint] 919Meeting Rooms IIHashIntervalPython
#重要題型
349 Intersection of Two ArraysHashPython
217Contains DuplicateHashArrayPython
C++ 內含 C++ set, unordered_set 用法整理
137Single Number IIHashPython
350Intersection of Two Arrays IIHashPython
2248Intersection of Multiple ArraysHashPython
290th Weekly Contest
49Group AnagramsHash (Anagrams)Python
217Contains DuplicateHash (Duplicate)Python
128Longest Consecutive SequenceHash (LCS)Python
136Single NumberHash, Bit ManipulationPython
⭐ Heap 相關題型 ⭐
264Ugly Number IIHeapPython
⭐ Stack 相關題型 ⭐
739Daily TemperaturesStackPython
496Next Greater Element IStackPython
503Next Greater Element IIStackPython
20Valid ParenthesesStack (Parentheses)Python
內含用 python List 組出 Stack, Queue 的方法整理
⭐ Two pointers 相關題型 ⭐
11Container With Most WaterTwo pointersPython
42Trapping Rain WaterTwo pointersPython
74Search a 2D Matrix Two pointersMatrixPython
141Linked List CycleTwo pointersLinked ListPython
142Linked List Cycle IITwo pointersLinked ListPython
內含 python while-else 用法介紹
283Move ZeroesTwo pointersPython
876Middle of the Linked ListTwo pointersPython
2260Minimum Consecutive Cards to Pick UpTwo pointers (快慢)Python
291st Weekly Contest
21Merge Two Sorted ListsTwo pointers (Merge)Linked ListPython
內含 python Linked List 基本操作 (for 新手教學)
88Merge Sorted Array Two pointers (Merge)Python C++ 內含 python while-else 用法說明
1Two SumTwo pointers (NSum)ArrayPython C++ 內有 Python list comprehesion / dict comprehesion 整理 / C++ map find 方法補充 (dict find)
153Sum Two pointers (NSum)ArrayPython
163Sum ClosestTwo pointers (NSum)Python
167Two Sum II – Input Array Is SortedTwo pointers (NSum)Python
[Lint] 382Triangle CountTwo pointers (NSum)Python
[Lint] 533Two Sum – Closest to TargetTwo pointers (NSum)Python
[Lint] 587Two Sum – Unique PairsTwo pointers (NSum)Python
5Longest Palindromic Substring Two pointers (Palindrome)Python C++ 內含 C++ string.substr() 用法筆記
9Palindrome NumberTwo pointers (Palindrome)Python
125Valid PalindromeTwo pointers (Palindrome)StringPython內含 python isalpha(), isalnum() 的整理
680Valid Palindrome IITwo pointers (Palindrome)Python
409Longest Palindrome
Two pointers (Palindrome)Python
647Palindromic SubstringsTwo pointers (Palindrome)Python
234Palindrome Linked ListTwo pointers (Palindrome)Linked ListPython
內含 reverse LinkedList 方法
75Sort ColorsTwo pointers (partition)Python
#重要題型
[Lint] 5Kth Largest ElementTwo pointers (partition)Python
#重要題型
[Lint] 31Partition ArrayTwo pointers (partition)Python
#重要題型
[Lint] 143Sort Colors IITwo pointers (partition)Python
#重要題型
[Lint] 461Kth Smallest Numbers in Unsorted ArrayTwo pointers (partition)Python
#重要題型
3Longest Substring Without Repeating CharactersTwo pointers (Sliding Window)Python
76 Minimum Window SubstringTwo pointers (Sliding Window)Python
239Sliding Window MaximumTwo pointers (Sliding Window)Python
⭐ 其他題型 / 待分類 ⭐
2Add Two NumbersLinked ListPython
7Reverse IntegerPython
19Remove Nth Node From End of ListLinked ListPython
36Valid SudokuPython
48Rotate ImageMatrixPython
621Task SchedulerPython
202Happy NumberPython
238Product of Array Except SelfPython
222Count Complete Tree NodesTreePython
674Longest Continuous Increasing SubsequencePython
435Non-overlapping IntervalsIntervalPython
88Merge Sorted ArrayPython
內含 python while-else 用法說明
2264Largest 3-Same-Digit Number in StringPython
292nd Weekly Contest
56Merge IntervalsIntervalPython
內含:python sorted key 搭配 lambda 的用法範例
57Insert IntervalIntervalPython
61Rotate ListLinked ListPython
2259Remove Digit From Number to Maximize ResultPython
291st Weekly Contest
53Maximum SubarrayPython
54Spiral MatrixPython
228Summary RangesPython
263Ugly NumberPython
203Remove Linked List ElementsLinked ListPython
內含 Linked List remove 操作 part 2 (for 新手教學)
206Reverse Linked ListLinked ListPython
內含 Linked List reverse 反轉操作 part 3 (for 新手教學)
189Rotate ArrayArrayPython
2185Counting Words With a Given PrefixStringPython
282nd Weekly Contest
134Gas StationPython
121Best Time to Buy and Sell StockPython
83Remove Duplicates from Sorted ListLinked ListPython
566Reshape the MatrixMatrixPython
內含 python array 初始化, index 操作與控制範例
2243Calculate Digit Sum of a StringPython
289th Weekly Contest
2244Minimum Rounds to Complete All TasksPython
289th Weekly Contest
2249Count Lattice Points Inside a CirclePython
290th Weekly Contest
⭐【喜歡我的文章嗎? 歡迎幫我按讚~ 讓基金會請創作者喝一杯咖啡!
如果喜歡我的文章,請幫我在下方【按五下Like】 (Google, Facebook 免註冊),會由 「LikeCoin」 贊助作者鼓勵繼續創作,讀者們「只需幫忙按讚,完全不用出錢」哦!

likecoin-steps
Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 728

★留個言吧!內容有誤或想要補充也歡迎與我討論!