LeetCode #88 Merge Sorted Array 解題思路及翻譯

LeetCode題目翻譯

英文原文如下

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

中文翻譯

給予你兩個整數陣列  nums1 跟 nums2 (非遞減排列)，以及兩個整數 m 跟 n ，分別代表了 nums1 跟 nums2 分別有幾個元素 (他們的長度)。

合併 nums1 跟 nums2 到一個陣列 (非遞減排列)

最後經過排序的陣列不用回傳，應該要被設在nums1 這個陣列。為了容納這個 ，nums1 的長度為 m + n ，前面的 m 個元素為要合併的，後面的 n 個元素則被設為  0 且應要忽略的。 nums2  的長度為 n。

天啊…這篇寫的跟文言文一樣，反正可以理解為要合併兩個Array就好。

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

進一步 : 可以回答出時間複雜度為  O(m + n)  的解答嗎?

解題思路

第一個方法也比較單純，先別管他的排序，合併起來之後再排

C# 解決方案

方案1

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        
        int cnt = 0;
        for(int i = m;i<nums1.Length;i++)
        {
            nums1[i] = nums2[cnt];
            cnt++;
        }
        Array.Sort(nums1);
    }
}

時間複雜度 : m-n次+Array.Sort ➡ O(n)+O(n log n)

⭐方案2

public class Solution {
    public void Merge(int[] nums1, int m, int[] nums2, int n) {
        
        int index = m+n-1;  //last index
        while(n>0)
        {
            if(m>0 && nums1[m-1]>nums2[n-1])
            {
                nums1[index] = nums1[m-1];
                m--;
            }
            else
            {
                nums1[index] = nums2[n-1];
                n--;
            }
            index --;
        }
    }
}

如題目所說，我們要做的就是把兩個陣列合併到 nums1 中。

在這個方法中，我們從nums1後面開始取代

因為nums1後面為0

最理想狀況 ➡ nums2 全部數字都比 nums1 大，只需要跑 n 次

最糟糕狀況 ➡ nums2最小的數字比 nums1 小，需要跑 m+n次 (全部)

時間複雜度 : O(n)

Java解決方案

方案1

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int cnt = 0;
        for(int i = m;i<nums1.length;i++)
        {
            nums1[i] = nums2[cnt];
            cnt++;
        }
        
        Arrays.sort(nums1); 
    }
}

運行時間 : 1ms

⭐方案2

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m+n-1;  //last index
        while(n>0)
        {
            if(m>0 && nums1[m-1]>nums2[n-1])
            {
                nums1[index] = nums1[m-1];
                m--;
            }
            else
            {
                nums1[index] = nums2[n-1];
                n--;
            }
            index --;
        } 
    }
}

運行時間 : 0ms

Python3 解決方案

方案1

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.
        """
        cnt = 0;
        while(m < len(nums1)):
            nums1[m] = nums2[cnt];
            cnt+=1
            m+=1
        nums1.sort();

⭐方案2

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.
        """
        index = m+n-1
        
        while(n>0):
            if(m>0 and nums1[m-1]>nums2[n-1]):
                nums1[index] = nums1[m-1];
                m-=1;
            
            else:
                nums1[index] = nums2[n-1];
                n-=1;
            
            index -=1;

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    var index = m+n-1;  //last index
    while(n>0)
    {
        if(m>0 && nums1[m-1]>nums2[n-1])
        {
            nums1[index] = nums1[m-1];
            m--;
        }
        else
        {
            nums1[index] = nums2[n-1];
            n--;
        }
        index --;
    } 
};

結論

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡可以的話，幫我的FaceBook 粉絲專頁按個讚，我會很感謝的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Merge Sorted Array – LeetCode

• LeetCode #1700 Number of Students Unable to Eat Lunch 吃不到午餐的學生數量
• LeetCode #1544 Make The String Great 讓字串變好
• LeetCode #977 Squares of a Sorted Array 已排序陣列的平方
• LeetCode #283 Move Zeroes 移動零
• LeetCode #997 Find the Town Judge 找到鎮上的法官