88. Merge Sorted Array

描述

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

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 greater or equal to m + n) to hold additional elements from 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]

解法

要求原地合并，列表 1 提供足够的空间，因此使用从后向前合并的策略保证前面的数据不会被覆盖。

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.
        """
        i = m - 1  # current locatin for nums1
        j = n - 1  # current locatin for nums2

        for k in range(len(nums1))[::-1]:
            if i < 0:  # nums1 is all out
                nums1[k] = nums2[j]
                j -= 1
            elif j < 0:  # j is all out, all the job should done
                break
            elif nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1

        # another for loop
        m = m - 1
        n = n - 1
        for k in range(len(nums1)):
            if n < 0:
                break
            if m < 0:
                nums1[:n+1] = nums2[:n+1]
                break
            elif nums1[m] > nums2[n]:
                nums1[~k] = nums1[m]
                m -= 1
            else:
                nums1[~k] = nums2[n]
                n -= 1

一个一行解法：

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # while n > 0: nums1[m+n-1], m, n = (nums1[m-1], m-1, n) if m and nums1[m-1] > nums2[n-1] else (nums2[n-1], m, n-1)

        while n > 0:
            nums1[m+n-1], m, n = (nums1[m-1], m-1, n) if m and nums1[m-1] > nums2[n-1] else (nums2[n-1], m, n-1)

因为是把 nums2 合并到 nums1，所以当 nums2 的元素都添加到 nums1 中适当位置的时候，原本的 nums1 中的元素本身有序，此时整个列表有序，这是循环终止的条件。当前处理元素的位置可以由 m + n - 1 取到，即剩余元素总个数减 1 就是当前位置的索引。

展开来写就是：

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        i, j, k = m - 1, n - 1, m + n - 1

        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

        if i < 0:       # Nothing to move if only nums1 remain, else move rest of nums2
            nums1[:k+1] = nums2[:j+1]

小结

Python 负数补码显示

>>> bin(-5)
'-0b101'
>>> bin(-5 % (1<<32))  # 移位表示显示位数
'0b11111111111111111111111111111011'

# 函数封装
def intToBin32(self, i):
    return (bin(((1 << 32) - 1) & i)[2:]).zfill(32)

def bin32ToInt(self, s):
    return int(s[1:], 2) - int(s[0]) * (1 << 31)

i 和 ~i

# i ~i
for i in range(10):
    print(i, ~i, bin(i), bin(~i % (1 << 8)))
# 0 -1 0b0000000 0b11111111
# 1 -2 0b0000001 0b11111110
# 2 -3 0b0000010 0b11111101
# 3 -4 0b0000011 0b11111100
# 4 -5 0b0000100 0b11111011
# 5 -6 0b0000101 0b11111010
# 6 -7 0b0000110 0b11111001
# 7 -8 0b0000111 0b11111000
# 8 -9 0b0001000 0b11110111
# 9 -10 0b001001 0b11110110

Python 使用 For 循环反向遍历可迭代对象

# for range[::-1]
print(range(10)[::-1]) # range(9, -1, -1)
for i in range(10)[::-1]:
    print(i, end=' ')
print()
# 9 8 7 6 5 4 3 2 1 0

# for range with ~i
for i in range(10):
    print(~i, end=' ')
print()
# -1 -2 -3 -4 -5 -6 -7 -8 -9 -10

列表使用切片原地赋值

# a[:k] = b[i, i+k]
a = [x for x in range(10)]
b = [x ** 2 for x in range(5)]
print(id(a), a)
a[:5] = b[:5]
print(id(a), a)
# 140668708919304 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 140668708919304 [0, 1, 4, 9, 16, 5, 6, 7, 8, 9]

引用

python – 以二进制补码表示格式化负整数

Python小技巧：负数的补码表示