【美團(tuán)面試題】合并兩個有序數(shù)組

題目描述

給你兩個有序整數(shù)數(shù)組 nums1 和 nums2，請你將 nums2 合并到 nums1 中，使 nums1 成為一個有序數(shù)組

劃重點(diǎn)

• 初始化 nums1 和 nums2 的元素數(shù)量分別為 m 和 n 。
• 你可以假設(shè) nums1 有足夠的空間（空間大小大于或等于 m + n）來保存 nums2 中的元素

示例

示例 1:

輸入： nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3輸出：[1,2,2,3,5,6]

提示：

-10^9 <= nums1[i], nums2[i] <= 10^9 nums1.length == m + n nums2.length == n

解題思路

兩個數(shù)組分別有序，且最終要輸出的是數(shù)組一解法如下

解法

解法一： 暴力法

將數(shù)組nums2中的元素全部添加到nums1中，對nums1做排序

解法二：倒插法

已知條件

Nums1 的剩余空間剛好可以存放nums2的元素

nums1和nums2都是有序的。

已知兩個數(shù)組的元素個數(shù)

通過分析一直條件我們可以發(fā)現(xiàn)，nums1存在一定的后置空間，因此我們可以考慮通過對兩個數(shù)組的末位元素進(jìn)行對比，然后從后往前插入到nums1中的方法。

所以我們可以用三個指針P0,P1,P2來遍歷數(shù)組：

P0： 記錄nums1的新元素位置

P1： 記錄nums1原數(shù)組的元素位置

P2： 記錄nums2原數(shù)組的元素位置

設(shè)置遍歷條件 (p1 >= 0 && p2 >= 0)

比較指針指向的元素大小，將較大的元素放入指針P0的位置，同時移動P0和較大元素的指針。

當(dāng)遍歷條件為 false時 存在三種情況

P1 == 0 P2 ==0 數(shù)組都遍歷完了

P1 == 0 P2 > 0 Nums2沒有遍歷完

P1 > 0 P2 ==0 Nums1沒有遍歷完

當(dāng)結(jié)果出現(xiàn)1和3時，nums1恰好是合并排序的最終結(jié)果

當(dāng)出現(xiàn)結(jié)果2時，說明nums2中還有剩余元素，所以繼續(xù)移動指針P1，將nums2剩余元素插入到nums1中就行

代碼實現(xiàn)

public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m - 1;int p2 = n - 1;int p0 = m + n - 1;while (p1 >= 0 && p2 >= 0) {if (nums1[p1] >= nums2[p2]) {nums1[p0] = nums1[p1];p1--;} else {nums1[p0] = nums2[p2];p2--;}p0--;}// 處理 nums2 沒有遍歷完的情況while (p2 >= 0) {nums1[p0--] = nums2[p2--];}}

復(fù)雜度分析

時間復(fù)雜度：

O(n + m)

空間復(fù)雜度：

O(1)

總結(jié)

以上是生活随笔為你收集整理的中数组的合并_【美团面试题】合并两个有序数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。