Javascript刷LeetCode: 088.合並兩個有序數組

前端想進大廠QAQ 2022-01-07 17:51:09 阅读数:244

javascript leetcode 有序

1. 題目

給你兩個按 非遞减順序 排列的整數數組 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 中。
複制代碼

2.解法一:直接合並後排序

var merge = function(nums1, m, nums2, n) {
nums1.splice(m, nums1.length - m, ...nums2);
nums1.sort((a, b) => a - b);
};
複制代碼

image.png

  • 複雜度分析:
    • 時間複雜度:不同瀏覽器對sort的實現不同,這裏按快速排序算,平均情况為O((m+n)log(m+n))

    • 空間複雜度:log(m + n)

3.解法二:雙指針法

/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */
var merge = function(nums1, m, nums2, n) {
let result = []
let nums1Index = nums2Index = 0
while(nums1Index < m && nums2Index < n) {
if(nums1[nums1Index] <= nums2[nums2Index]) {
result[nums1Index + nums2Index] = nums1[nums1Index++]
} else {
result[nums1Index + nums2Index] = nums2[nums2Index++]
}
}
while(nums1Index < m) {
result[nums1Index + nums2Index] = nums1[nums1Index++]
}
while(nums2Index < n) {
result[nums1Index + nums2Index] = nums2[nums2Index++]
}
const length = result.length
for(let i = 0; i < length; i++) {
nums1[i] = result[i]
}
};
複制代碼
  • 複雜度分析:
    • 時間複雜度:** O(m+n)** 因為最多只用遍曆一邊num1和num2兩個數組

    • 空間複雜度:O(m+n) 需要建立長度為 m+n 的中間數組

image.png

4.解法三:雙指針優化(逆向雙指針)

/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */
var merge = function(nums1, m, nums2, n) {
let nums1Index = m - 1
let nums2Index = n - 1
while(nums1Index >=0 && nums2Index >= 0) {
if(nums1[nums1Index] >= nums2[nums2Index]) {
nums1[nums1Index + nums2Index + 1] = nums1[nums1Index--]
} else {
nums1[nums1Index + nums2Index + 1] = nums2[nums2Index--]
}
}
while(nums2Index >= 0) {
nums1[nums2Index] = nums2[nums2Index--]
}
};
複制代碼
  • 複雜度分析:
    • 時間複雜度: O(m+n) 因為最多只用遍曆一邊num1和num2兩個數組

    • 空間複雜度:O(1) 直接對數組 nums1 原地修改,不需要額外空間。

image.png

5.總結

從結果看上去好像解法一更快,但還是要從複雜度分析上來看

  • 解法一: 時間複雜度O((m+n)log(m+n)) 空間複雜度log(m + n)
  • 解法二: 時間複雜度O(m+n) 空間複雜度O(m+n)
  • 解法三: 時間複雜度O(m+n) 空間複雜度O(1)

因此解法三更優

ps:但是平時在開發中數據量不太會影響效率的時候,我會用第一種,因為實在太簡潔了

版权声明:本文为[前端想進大廠QAQ]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071751092717.html