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

LeetCode #88 合併兩個已排序陣列。含題目翻譯、C#,Java,Python3,JavaScript 解答 (不同的時間複雜度 )

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 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就好。

LeetCode #88 Example picture
LeetCode #88 Constraints picture

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

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *