Python を使えるようになりたいので、勉強した内容を Output して、学びの解像度を上げたいと思います。
今回説く問題は、こちら。
--- 問題 ---
88. Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
Constraints:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
==
以下の問題は、
--- 日本語訳 ---
Non-Decresing の順番に並べられた 2 つの入れるがあります。
それぞれは nums1 と nums2 という名前です。
nums1 と nums2 の入れるの要素数を表すのは、m,n の 2 つの整数で表されます。
nums1 と nums2 の配列上の数値を比較して、Non-Decresing の順番 (つまり、昇順)
配列の様子数の大 -> 小の流れに沿って、配列の数字を入れ替える。
そして最終的な結果は、nums1 上に格納して出力が求められている。
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
--- 参考回答内容 ---
# ここで予め扱う変数を宣言します。(nums1, m, nums2, n)
def merge(nums1, m, nums2, n):
# nums1 と nums2 の最後の有効要素から比較を開始
nums1, nums2 の配列は昇順で並んだ状態で渡されるので、後ろの値から比較をするにあたり、
nums1, nums2 の最後の数値を指す為に、有効な要素数の m,n を 1 引いた値にする。
∵配列の要素数は 0 から始まるので、要素数を 1 引く必要がある。
p1, p2 = m - 1, n - 1
# 最後の求められる回答は、mとn の有効な要素数分を nums1 の配列に全て格納して出力する必要
# があるので、m と n の有効要素数を足して、-1 する。(∵ 配列の要素数は 0 からスタートする為 )
# の末尾から値を挿入するためのポインタ
p = m + n - 1
# nums2 の要素をすべて処理するまで繰り返す
# nums1 [p1] と nums2 [p2] を比較する為、p2>0 であれば次に進み、
nums1[p1] > nums2[p2]が成立するなら、nums1[p1] を追加するし、
nums1[p1] > nums2[p2] が成立しないなら、nums2[p2]: を追加して
nums1[p] を 1 つ減らして、処理を継続する。
while p2 >= 0:
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
具体的な入力データ
nums1 = [1, 2, 3, 0, 0, 0] # nums1 のサイズは m + n
m = 3 # nums1 の有効要素数
nums2 = [2, 5, 6] # nums2 の配列
n = 3 # nums2 の要素数
マージ関数を呼び出し
merge(nums1, m, nums2, n)
結果を出力
print("マージ後の nums1:", nums1)