程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 88 Merge Sorted Array(合並排序數組)(*)

LeetCode 88 Merge Sorted Array(合並排序數組)(*)

編輯:C++入門知識

LeetCode 88 Merge Sorted Array(合並排序數組)(*)


翻譯

給定兩個排序的整型數組nums1和nums2,將nums2合並到nums1成一個排序數組。

批注:
你可以假設nums1中有足夠的空間(空間大於或等於m+n)來存放來自nums2的額外元素。
nums1和nums2的初始空間分別是m和n。

原文

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.

分析

有一種思路是,另外設置一個數組,然後將nums1和nums2中的數據按大小逐個添加到這個新數組中,最後將這個數組整個賦值給nums1,不過像是作弊一樣,題意說了是要並到nums1中的,這樣一來nums1並沒有變化。

所以,繼續想新的方法……

先來理一理,有如下這些關系:

1,m和n表示的是nums1和nums2中已經初始化的元素數量,
而並非nums1和nums2的空間大小,也就是說nums1中空間足夠大,
但其中m個空間設置了該設的值,我們在本題中稱它為有效數目

2,由1得出合並後的總的有效數目為m+n

3,因為都是從0開始,所以nums1和nums2的最後一個元素的索引分別是m-1和n-1,
合並後的nums1的最後一個元素的索引應該是m+n-1

4,我們是將nums2並入nums1,所以整體的循環可以從nums2開始

5,下面我會闡述為什麼內部的循環要從nums1的尾部開始:

因為這是vector數組而不是鏈表,它們是有索引的,索引是從前到後的(從0到m-1)
如果在數組前方添加一個數字,那麼其後的所有元素都需要往後挪一步
而如果在後方添加一個數字,前面的則不需要移動。
至於為什麼不擔心後方空間問題,因為題目說了給nums1的空間足夠大。

這裡寫圖片描述

原諒我沒有再給數組畫豎線以區分每個格子,相信大家都懂的,我已經盡力了,哈哈……

看代碼……

代碼

class Solution {
public:
    void merge(vector &nums1, int m, vector &nums2, int n) {
        int i = m - 1, j = n - 1, position = m + n - 1;
        while (j >= 0) {
            nums1[position--] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
        }
    }
};

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved