Inserting Items Into an Array

本文蒐集

• LeetCode 1089
• LeetCode 88

LeetCode 1089: Duplicate Zeros

Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array in place, do not return anything from your function.

Example 1:

Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: [1,2,3]
Output: null
Explanation: After calling your function, the input array is modified to: [1,2,3]

Note:

• 1 <= arr.length <= 10000
• 0 <= arr[i] <= 9

我的解答

q1089.pyview raw
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        i = 0
        while i < (len(arr)-1):
            if arr[i] == 0:
                j = len(arr)-1
                while i < j:
                    arr[j] = arr[j-1]
                    j -= 1
                i += 2
            else:
                i += 1

• Time complexity: O(\(n^2\))
• space complexity: O(1)

簡潔 code

q1089_簡潔.pyview raw
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        i=0
        while i<len(arr):
            if arr[i]==0:
                arr.pop() # O(1)
                arr.insert(i+1,0) # O(N)
                i+=2
            else:i+=1

不建議

空間換時間

q1089_空間換時間.pyview raw
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        len_arr=len(arr)
        rst=[]
        for num in arr:
            if num==0:
                rst.append(0)
                rst.append(0)
            else:rst.append(num)
            if len(rst)>=len_arr:
                arr[:]=rst[:len_arr]
                # arr=rst[:len_arr] this do not work
                break

盡量把append()和[:]換掉

• Time complexity: O(n)
• space complexity: O(n)

LeetCode 88: Merge Sorted Array

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

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

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]

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[i] <= 109

我的解法

q88.pyview raw
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if n == 0:
            return
        elif m == 0:
            nums1[:n] = nums2[:]
            return
        else:
            temp = [0] * m
            temp[:] = nums1[:m]
            i, j, k = 0, 0, 0
            while k < m+n:
                if temp[i] < nums2[j]:
                    nums1[k] = temp[i]
                    k += 1
                    i += 1
                    if i == m:
                        break
                else:
                    nums1[k] = nums2[j]
                    k += 1
                    j += 1
                    if j == n:
                        break
            if i == m:
                nums1[k:] = nums2[j:]
            else:
                nums1[k:] = temp[i:]

• Time complexity: O(n)
• space complexity: O(1)

神人解法

q88_改進.pyview raw
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        while n > 0:
            if m <= 0 or nums2[n-1] >= nums1[m-1]:  
                nums1[m+n-1] = nums2[n-1]
                n -= 1
            else:
                nums1[m+n-1] = nums1[m-1]
                m -= 1

• Time complexity: O(n)
• space complexity: O(1)