LeetCode

35 Search Insert Position

Problem

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with $O(log n)$ runtime complexity.

My Solution

code

class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
    if target < nums[0]:
        return 0
    elif target > nums[-1]:
        return len(nums)
    left = 0
    right = len(nums) - 1
    mid = left + (right - left) //2
    while mid < right and left < mid:
        if target == nums[mid]:
            return mid
        elif target < nums[mid]:
            right = mid
            mid = left + (right - left) //2
        else:
            left = mid
            mid = left + (right - left) //2
    if target == nums[mid]:
        return mid
    elif nums[left] < nums[mid]:
        return left + 1
    else:
        return mid + 1

思路

1. 先避免Conner case 如果target 比最左边的还小 或者 最右边的还大 直接return 0 或者 len(nums)
2. 确定target在nums中后，按照二分法去逼近target。在while循环结束后，可以保证target在[left, right]内，且区间长度为2。
3. 如果 target == nums[mid]，则直接return mid。 利用mid来判断target是被夹在left和mid间 还是 mid和right间。
   • left < mid: target 插入 mid (left+1)；
   • mid < right: target 插入 mid+1（right）。

复杂度分析

时间复杂度: $O(log(n))$ where $n= len(nums) $
空间复杂度分析: $O(1)$

989 Add to Array-Form of Integer

Problem

The array-form of an integer num is an array representing its digits in left to right order.

• For example, for num = 1321, the array form is [1,3,2,1]. Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.

My Solution

code

class Solution:
def addToArrayForm(self, num: List[int], k: int) -> List[int]:
    sum_list = []
    carry = 0 
    for i in range(len(num)):    
        res = k%10
        curr_sum = res + num[-(1+i)] + carry
        if curr_sum > 9:
        curr_sum = curr_sum%10
        carry = 1
        else:
        carry = 0
        sum_list.insert(0,curr_sum)
        k = k//10
    while k:
        res = k%10
        curr_sum = res + carry
        if curr_sum > 9:
        curr_sum = curr_sum%10
        carry = 1
        else:
        carry = 0
        sum_list.insert(0,curr_sum)
        k = k//10
    if carry:
        sum_list.insert(0, 1)
    return sum_list

思路

1. 先遍历数组num， 利用carry 和整除 求余，计算干净 num。
2. 如果遍历数组后， k 非零，继续将 k 转化为数组放到前面。
3. 最后，如果 carry非零，再一次放到前面。

复杂度分析

时间复杂度: $O(n)$ where $n= max(len(nums), len(k_array)) $
空间复杂度: $O(n)$ where $n= max(len(nums), len(k_array)) $

注意如果想转化为数字相加，注意浮点数问题。

Better Solution

class Solution: 
def addToArrayForm(self, A: List[int], K: int) -> List[int]:
    carry = 0
    for i in range(len(A) - 1, -1, -1):
        A[i], carry = (carry + A[i] + K % 10) % 10, (carry + A[i] + K % 10) // 10
        K //= 10
    B = []
    # 如果全部加完还有进位，需要特殊处理。 比如 A = [2], K = 998
    carry = carry + K
    while carry:
        B = [(carry) % 10] + B
        carry //= 10
    return B + A

思路

如果你没做出来这道题，不妨先试试 66. 加一，那道题是这道题的简化版，即 K = 1 的特殊形式。

这道题的思路是 从低位到高位计算，注意进位和边界处理。 细节都在代码里。

为了简化判断，我将 carry（进位） 和 K 进行了统一处理，即 carry = carry + K

复杂度分析

令 N 为数组长度。

时间复杂度：$O(N+max(0, K-N)^2) $ 空间复杂度：$O(max(1,K−N))$

26 Remove Duplicates from Sorted Array

Problem

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

My Solution

code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return len(nums)
        i = 0
        while i < len(nums)-1:
            if nums[i] == nums[i+1]:
                nums.pop(i+1)
            else:
                i += 1
        return len(nums)

思路

依次比较current和current+1，重复的直接pop掉。

复杂度分析

时间复杂度: $O(n)$ where $n=len(nums)$.
空间复杂度: $O(1)$ since the operation is in place

Better Solution

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for j in range(len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        return i + 1

对比的话，这个快慢指针的判断比较简洁 前$i+1$个都是需要的。