- 題目：合并兩個有序陣列
力扣鏈接：合并兩個有序陣列
給你兩個按 非遞減順序 排列的整數陣列
nums1和nums2，另有兩個整數m和n，分別表示nums1和nums2中的元素數目請你 合并
nums2到nums1中，使合并后的陣列同樣按 非遞減順序 排列
- 注意：
最終，合并后陣列不應由函式回傳，而是存盤在陣列
nums1中，為了應對這種情況，nums1的初始長度為m + n，其中前m個元素表示應合并的元素，后n個元素為0，應忽略，nums2的長度為n
- 示例：
- 提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
- 進階：你可以設計實作一個時間復雜度為 O(m + n) ，空間復雜度為O(1)演算法解決此問題嗎？
空間復雜度為O(1):即不創建其他陣列
時間復雜度為 O(m + n)：即一層回圈
- 思考要點：
陣列一和陣列二一個一個比較，決定放的位置的次序
如果是從前合并則會覆寫資料，從后則不會
參考代碼：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
//記錄第一個陣列和第二個最后一位有效資料
int end1 = m - 1, end2 = n - 1;
//標記第一個陣列的最后位置
int end = m + n - 1;
//有一個小于零則陣列越界
while(end1>=0&&end2>=0)
{
if (nums1[end1] >= nums2[end2])
{
//先賦值，后自增
nums1[end--] = nums1[end1--];
}
else
{
nums1[end--] = nums2[end2--];
}
}
//end2越界時，陣列一的資料已經在合并陣列內且不用處理了
//end1越界時，陣列二還有資料未合并
while (end2>=0)
{
nums1[end--] = nums2[end2--];
}
}
執行結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/317915.html
標籤：其他