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.
Mergenums1 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 --;
}
}
}
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};