有了域名 做網(wǎng)站seo查詢愛站網(wǎng)
🎗? 主頁:小夜時雨
🎗?專欄:動態(tài)規(guī)劃
🎗?如何活著,是我找尋的方向
目錄
- 1. 題目解析
- 2. 代碼
1. 題目解析
題目鏈接: https://leetcode.cn/problems/merge-sorted-array/description/
本道題是歸并排序的核心代碼區(qū)間, 所以還是十分重要的, 接下來我們來分析一下這道題目.
- 首先我們注意到這個是兩個非遞減的整數(shù)數(shù)組,那么很自然的一個想法就是從頭開始遍歷兩個數(shù)組,誰小取出來排隊(duì)即可。
- 取出來排隊(duì)這個操作我們巨化為創(chuàng)建一個輔助數(shù)組,將數(shù)組中二者比較小的放入到這個輔助數(shù)組中, 直到遍歷結(jié)束。
- 最后再將輔助數(shù)組拷貝到原始數(shù)組中即可。整體的思路還是比較符合實(shí)際我們進(jìn)行比較排序的情況的。
具體實(shí)現(xiàn)過程:
- 創(chuàng)建一個 m + n 的輔助數(shù)組, 變量 cur1, cur2, i。
- cur1 遍歷數(shù)組nums1, cur2遍歷數(shù)組nums2,i 記錄輔助數(shù)組填表的位置。
- cur1 和 cur2 while 循環(huán)同時遍歷各自的數(shù)組, 比較二者的數(shù),誰小放入到輔助數(shù)組中去,同時指針要向后移動一位。
- while(cur1 <= m - 1 && cur2 <= n - 1), 注意循環(huán)條件是并的關(guān)系, 所以當(dāng) while 循環(huán)跳出的時候, cur1 <= m - 1 或者 cur2 <= n - 1 有一個已經(jīng)提前到數(shù)組的末尾了, 那還有另一個數(shù)組沒有遍歷完。
- 所以我們要接著遍歷另外一個沒有遍歷完的,把數(shù)直接添加到輔助數(shù)組的后面(直接添加是因?yàn)檫@兩個都是有序數(shù)組)
- 由于并不知道是哪一個指針先遍歷完,所以要寫兩個判斷。這里的判斷我們繼續(xù)用 while 循環(huán)繼續(xù)代替。
- 遍歷原數(shù)組把輔助數(shù)組中的數(shù)拷貝到原數(shù)組中即可。
2. 代碼
看下面的代碼對照著上面的流程解析會更加的清楚。
其實(shí)還有一種直接在原數(shù)組中進(jìn)行拷貝的, 并不需要用到輔助數(shù)組,但是為了和后續(xù)歸并排序聯(lián)系在一起,我們此處只介紹了用輔助數(shù)組的具體過程,這個也更加容易理解(我們把不用輔助數(shù)組的代碼也貼在最后面)。
// 這個就是歸并排序的核心部分。 必須要會// 歸并排序中用的就是這個思想。public void merge(int[] nums1, int m, int[] nums2, int n) {int[] tmp = new int[m + n];int cur1 = 0, cur2 = 0, i = 0;、// 合并兩個有序數(shù)組到輔助數(shù)組中while(cur1 <= m - 1 && cur2 <= n - 1) tmp[i++] = nums1[cur1] <= nums2[cur2] ? nums1[cur1++] : nums2[cur2++];// 處理還沒有遍歷完的數(shù)組. 上面條件是并的關(guān)系,所以下面的while循環(huán)只會有一個執(zhí)行while(cur1 <= m - 1) tmp[i++] = nums1[cur1++];while(cur2 <= n - 1) tmp[i++] = nums2[cur2++];// 遍歷原數(shù)組, 還原輔助數(shù)組到原數(shù)組中for(int j = 0; j < m + n; j++) {nums1[j] = tmp[j];}return;}
不需要用到拷貝數(shù)組的寫法代碼(建議學(xué)會上面那一種寫法,容易理解):
public void merge2(int[] nums1, int m, int[] nums2, int n) {//有一點(diǎn)利用歸并排序的思想int i = m -1;int j = n -1; //分別記錄有效數(shù)據(jù)的最后一位int k = m + n - 1; //記錄nums1數(shù)組的最后一個位置// && 邏輯與 是為了保證索引不越界while(i >= 0 && j >= 0) {if (nums1[i] <= nums2[j]) {nums1[k] = nums2[j];k--;j--;}else {nums1[k] = nums1[i];k--;i--;}} // 走到這說明i 和 j有一個不為0,其中不用管數(shù)組1中的數(shù)據(jù),因?yàn)橐截惖綌?shù)組1中,本身就是有序的。// 只需要判斷 數(shù)組2的情況就行,把數(shù)組2中的數(shù)據(jù)拷貝到數(shù)組1中去 // 即是有可能數(shù)組1走完了,數(shù)組2中還有數(shù)據(jù)while(j >= 0) {nums1[k] = nums2[j];k--;j--;}}
🎗?🎗?🎗? 好啦,到這里有關(guān)本題的分享就沒了,如果感覺做的還不錯的話可以點(diǎn)個贊,關(guān)注一下,你的支持就是我繼續(xù)下去的動力,我們下期再見,拜了個拜~ ☆*: .。. o(≧▽≦)o .。.:*☆