題目大意

合并兩個(gè)已經(jīng)有序的數(shù)組，結(jié)果放在第一個(gè)數(shù)組中，第一個(gè)數(shù)組假設(shè)空間足夠大。要求算法時(shí)間復(fù)雜度足夠低。

解題思路

1.可以先吧nums2的數(shù)據(jù)全放在nums1 里面，然后再對nums1進(jìn)行排序，時(shí)間復(fù)雜度O((m + n)log(m+n))?

2.可以復(fù)制一份nums1的前m個(gè)數(shù)，然后從前往后依次對比nums1，nums2，時(shí)間復(fù)雜度O(m+n),空間復(fù)雜度O(m)

3.為了不大量移動(dòng)元素，就要從2個(gè)數(shù)組長度之和的最后一個(gè)位置開始，依次選取兩個(gè)數(shù)組中大的數(shù)，從第一個(gè)數(shù)組的尾巴開始往頭放，只要循環(huán)一次以后，就生成了合并以后的數(shù)組了。時(shí)間復(fù)雜度O(m+n)

????public?void?merge(int[]?nums1,?int?m,?int[]?nums2,?int?n)?{

????????int?i?=?m?-?1;

????????int?j?=?n?-?1;

????????int?index?=?m?+?n?-?1;

????????while?(i?>?-1?||?j?>?-1)?{

????????????if?(i?>?-1?&&?j?>?-1)?{

????????????????if?(nums1[i]?>?nums2[j]){

????????????????????nums1[index]?=?nums1[i];

????????????????????i--;

????????????????}?else?{

????????????????????nums1[index]?=?nums2[j];

????????????????????j--;

????????????????}

????????????}?else?if?(i?>?-1)?{

????????????????nums1[index]?=?nums1[i];

????????????????i--;

????????????}?else?{

????????????????nums1[index]?=?nums2[j];

????????????????j--;

????????????}

????????????index--;

????????}

????}