[Leetcode] Merge Sorted Array 合并數組

quietin 發布于2019-08-14 12:26 / 1248人閱讀

摘要：但是如果我們從后往前，合并到第一個數組的最后，則不用位移。注意將和都先減，用和來代表下標，避免兩個數組為空時拋出空指針異常。

Merge Sorted Array 最新更新請見：https://yanjia.me/zh/2019/02/...

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

倒序存儲 復雜度

時間 O(N+M) 空間 O(1)

思路

提示第一個數組的大小足以裝兩個數組，所以自然想到把兩個數組都合并到第一個數組中，但是第一個數組前面都是有用的信息，如果直接從前面加，我們得將后面所有的數都位移。但是如果我們從后往前，合并到第一個數組的最后，則不用位移。

注意

將m和n都先減1，用m和n來代表下標，避免兩個數組為空時拋出空指針異常。

代碼

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        m = m - 1;
        n = n - 1;
        int i = m + n + 1;
        while(m >= 0 || n >= 0){
            if(m < 0){
                nums1[i--] = nums2[n--];
            } else if(n < 0) {
                nums1[i--] = nums1[m--];
            } else {
                nums1[i--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
            }
        }
    }
}

GPU云服務器云服務器 sorted-array array_merge() array_merge 數組array

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64472.html

leetcode88 Merge Sorted Array

摘要：題目要求將兩個有序數組合并至其中一個數組并且該新數組仍然有序。所以我們可以換一種思維方式，從大至小遍歷，這樣可以將較大的元素直接填入當前的位置而且不用考慮移動其它的元素。題目要求 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: You...

taohonghui 2019-08-14 18:36 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 之 JavaScript 解答第23題 —— 合并K個有序鏈表（Merge K S

摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關聯原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治算法跟動態規劃的明顯區別。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿題目：Merge K...

zhou_you 2019-08-23 16:53 評論0 收藏0
leetcode 88 Merge Sorted Array

摘要：題目假設數組的長度大于需要排序的元素數量數組的后位為。解法看到這道題時一種常規思路可能是，從頭遍歷兩個數組，將的元素插入到的合適的位置。題目詳情 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. 題目的意思是，輸入兩個已經排好序的數組nums1和nu...

bbbbbb 2019-08-15 13:39 評論0 收藏0