題目： 給你兩個按 非遞減順序 排列的整數數組 nums1 和 nums2，另有兩個整數 m 和 n ，分別表示 nums1 和 nums2 中的元素數目。 請你 合併 nums2 到 nums1 中，使合併後的數組同樣按 非遞減順序 排列。 註意：最終，合併後數組不應由函數返回，而是存儲在數組 n ...
題目：
給你兩個按 非遞減順序 排列的整數數組 nums1 和 nums2，另有兩個整數 m 和 n ，分別表示 nums1 和 nums2 中的元素數目。
請你 合併 nums2 到 nums1 中，使合併後的數組同樣按 非遞減順序 排列。
註意：最終，合併後數組不應由函數返回，而是存儲在數組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合併的元素，後 n 個元素為 0 ，應忽略。nums2 的長度為 n 。
示例 1：
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
解釋：需要合併 [1,2,3] 和 [2,5,6] 。
合併結果是 [1,2,2,3,5,6] ，其中斜體加粗標註的為 nums1 中的元素。
示例 2：
輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
解釋：需要合併 [1] 和 [] 。
合併結果是 [1] 。
示例 3：
輸入：nums1 = [0], m = 0, nums2 = [1], n = 1
輸出：[1]
解釋：需要合併的數組是 [] 和 [1] 。
合併結果是 [1] 。
註意，因為 m = 0 ，所以 nums1 中沒有元素。nums1 中僅存的 0 僅僅是為了確保合併結果可以順利存放到 nums1 中。
提示：
nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109
進階：你可以設計實現一個時間複雜度為 O(m + n) 的演算法解決此問題嗎？
解：
① 解題思路：先將數組2放到數組1後半部分，再對數組1進行冒泡排序。時間複雜度：O（n+（m+n）方）
// 題目：給你兩個按 非遞減順序 排列的整數數組 nums1 和 nums2，另有兩個整數 m 和 n
// 分別表示 nums1 和 nums2 中的元素數目
// 請你合併 nums2 到 nums1 中，使合併後的數組同樣按 非遞減順序 排列。
//
// 註意：最終，合併後數組不應由函數返回，而是存儲在數組 nums1 中。
// 為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合併的元素，後 n 個元素為 0 ，應忽略。
// nums2 的長度為 n 。
class Solution {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
// 合併nums1、nums2，m，n分別代表對應數組的元素數目
// 先將數組2放到數組1後半部分，時間複雜度O(n)
for (int i = m; i < m + n; i++) {
nums1[i] = nums2[i - m];
}
// 對數組1進行冒泡排序,時間複雜度O((m+n)方)
for (int i = 0; i < m + n - 1; i++) {
for (int j = i + 1; j < m + n; j++) {
int temp;
if (nums1[i] > nums1[j]) {
temp = nums1[i];
nums1[i] = nums1[j];
nums1[j] = temp;
}
}
}
}
public static void main(String[] args) {
// 數組的兩種初始化方式
int[] nums1 = {4, 2, 3, 0, 0, 0};
int[] nums2 = new int[]{2, 5, 6};
merge(nums1, nums1.length - nums2.length, nums2, nums2.length);
// 列印合併後數組
for (int i = 0; i < nums1.length; i++) {
System.out.print(nums1[i] + " ");
}
}
}
兩個知識點補充：
-
非遞減排列：數列遞減，但裡面的元素可以重覆出現
1，2，3：遞增排列
3，2，1：遞減排列
1，1，2，3，3，3：非遞減排列
3，3，2，1，1 : 非遞增排列 -
Java數組初始化：兩種初始化方式如下
int[] nums1 = {4, 2, 3, 0, 0, 0}; int[] nums2 = new int[]{2, 5, 6};
② 解題思路：對①的冒泡進行修改，換成調用函數排序
import java.util.Arrays;
class Solution {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
// 合併nums1、nums2，m，n分別代表對應數組的元素數目
// 先將數組2放到數組1後半部分，時間複雜度O(n)
for (int i = m; i < m + n; i++) {
nums1[i] = nums2[i - m];
}
// **調用函數排序數組**
Arrays.sort(nums1);
}
public static void main(String[] args) {
// 數組的兩種初始化方式
int[] nums1 = {4, 2, 3, 0, 0, 0};
int[] nums2 = new int[]{2, 5, 6};
merge(nums1, nums1.length - nums2.length, nums2, nums2.length);
}
}
③ 解題思路：雙指針，利用數組 nums1與 nums2已經被排序的性質,時間複雜度是O(m+n)，空間複雜度
import java.util.Arrays;
class Solution {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
// 合併nums1、nums2，m，n分別代表對應數組的元素數目
int p1 = 0, p2 = 0; // 雙指針，分別指向當前排序的nums1、nums2的位置
int[] num = new int[m + n];
for (int i = 0; i < m + n; i++) {
if(p1 == m){ //nums1已經用完啦
num[i]=nums2[p2++];
continue;
}
if(p2 == n){ //nums2已經用完啦
num[i]=nums1[p1++];
continue;
}
if (nums1[p1] < nums2[p2]) {
num[i] = nums1[p1++];
} else {
num[i] = nums2[p2++];
}
}
System.arraycopy(num, 0, nums1, 0, nums1.length); //排序後num賦值給nums1
}
public static void main(String[] args) {
// 數組的兩種初始化方式
int[] nums1 = {1, 2, 3, 0, 0, 0};
int[] nums2 = new int[]{2, 5, 6};
merge(nums1, nums1.length - nums2.length, nums2, nums2.length);
// 列印合併後數組
for (int i = 0; i < nums1.length; i++) {
System.out.print(nums1[i] + " ");
}
}
}
④ 解題思路：逆雙指針，③的改進，因為nums1後部分為0，為了節省空間，可以不用新建num，直接對nums1從後往前進行插入
class Solution {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
// 合併nums1、nums2，m，n分別代表對應數組的元素數目
int p1 = m - 1, p2 = n - 1; // 逆雙指針，分別指向當前排序的nums1、nums2最後的位置
for (int i = m + n - 1; i >= 0; i--) {
if (p1 == -1) { //如果p1用完啦
nums1[i] = nums2[p2--];
continue;
}
if (p2 == -1) { //如果p2用完啦
nums1[i] = nums1[p1--];
continue;
}
if (nums1[p1] > nums2[p2]) {
nums1[i] = nums1[p1--];
} else {
nums1[i] = nums2[p2--];
}
}
}
public static void main(String[] args) {
// 數組的兩種初始化方式
int[] nums1 = {1, 2, 3, 0, 0, 0};
int[] nums2 = new int[]{2, 5, 6};
merge(nums1, nums1.length - nums2.length, nums2, nums2.length);
// 列印合併後數組
for (int i = 0; i < nums1.length; i++) {
System.out.print(nums1[i] + " ");
}
}
}
總結
以上分別是讀題之後的寫法，瞭解解題思路之後的實現情況。
本題較為簡單，但花費時間還是有點多，對java的函數和一些基礎使用方法還是不夠熟悉，中間還出現了一些數組越界的問題。
除了最後一種方法，應該還有其他的更便捷的解題思路，下次再看這題的話希望能有新的思路。
