LeetCodeに毎日挑戦してみた 88. Merge Sorted Array(Python、Go)


Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門+アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

20問目(問題88)

88. Merge Sorted Array

問題内容

Given a sorted linked list, delete all duplicates such that each element appear only once.

Note:

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

(日本語訳)

2つのソートされた整数配列nums1nums2与えられた場合nums2を1つのソートされた配列としてnums1にマージします。

注意:

  • で初期化要素の数nums1nums2であり、M及びnは、それぞれ。
  • あなたがいると仮定してもよいnums1に十分なスペース(ある大き有する 同じM + Nからの追加要素を保持する)nums2を

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

Constraints:

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

考え方

  1. targetのm,nを起点にしてループを回します

  2. Nums1,nums2の大小を判断し、nums1の後ろから代入していきます

  3. mが先に0になった場合はnums2の残りを代入していきます

  • 解答コード
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        while m > 0 and n > 0:
            if nums1[m-1] > nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        while n > 0:
            nums1[n-1] = nums2[n-1]
            n -= 1
  • Goでも書いてみます!
import "sort"

func merge(nums1 []int, m int, nums2 []int, n int) {
    nums1 = append(nums1[0:m], nums2[0:n]...)
    sort.Ints(nums1)
    return
}