1. Two Pointers Method
该方法是许多与 Array 相关的算法问题的绝对核心
旨在通过构建左、右两个指针来提升算法效率:
- 初始化左、右指针分别指向数组的最左、最右端
- 在遍历的过程中不断右移左指针、左移右指针，直至右指针的 index 大于左指针
1.1 Two Sum
需求: 在目标数组 nums 中找出两个元素，使他们的相加之和等于 target
nums=[1, 7, 6, 3, 9], target=9
twoSum(nums, target) >>> [6, 3]
非常经典的通过 Two Pointers Method 来降低时间复杂度的问题
Solution 1: Original ($O(n^2)$)
首先来分析一下最传统的嵌套双循环遍历
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [nums[i], nums[j]]
nums = [1, 7, 6, 3, 9]
twoSum(nums, 9) >>> [6, 3]
该算法的时间复杂度为 $O(n^2)$，存在大量浪费的空间，例如:
- 如果 $x_i + x_j > \text{target}$，那么在
X[j+1:]中所有大于 $x_j$ 的没必要考虑 - 如果 $x_i + x_j < \text{target}$，那么在
X[j+1:]中所有小于 $x_j$ 的没必要考虑
Solution 2: Two Pointers ($O(n\log n)$)
因此我们先可以对数组 nums 做排序 $O(n\log n)$，再使用 Two Pointers Method:
- 设置左、右两个指针分别指向升序数组的左右两端
- 如果左、右指针对应元素的和大于 target，那么就把右指针左移一格
- 如果左、右指针对应元素的和小于 target，那么就把左指针右移一格
从而成功降低了时间复杂度 $O(n\log n)+O(n)\implies O(n\log n)$
def twoSum(nums, target):
nums.sort() # O(nlogn)
left, right = 0, len(nums)-1
while left < right:
if nums[left] + nums[right] < target:
left += 1
elif nums[left] + nums[right] > target:
right -= 1
else: # nums[left] + nums[right] == target
return [nums[left], nums[right]]
return []
1.2 Three Sum
nums = [1, 7, 6, 3, 9]
threeSum(nums, 19) >>> [7, 9, 3]
非常类似于 Two Sum，Three Sum 相当于先固定一个元素，并更新一下 target，然后对剩下的所有元素做 Two Sum
时间复杂度 $O(n\log n)+O(n^2)\implies O(n^2)$
def threeSum(nums, target):
nums.sort()
for i in range(len(nums)-2):
target_temp = target - nums[i]
result = twoSum(nums[i+1:], target_temp)
if result is not None:
result.append(nums[i])
return result
1.3 Reverse Array
nums = [1, 7, 6, 3, 9]
reverseArray(nums) >>> [9, 3, 6, 7, 1]
def reverseArray(arr):
left, right = 0, len(arr)-1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
1.4 Odd Even Sort
需求: 把目标数组 nums 中所有奇数都放在偶数的左边
nums = [2, 7, 6, 3, 9]
oddEvenSort(nums) >>> [9, 7, 3, 6, 2]
def oddEvenSort(nums):
left, right = 0, len(nums)-1
while left < right:
while left < right and nums[left] % 2 == 1:
left += 1
while left < right and nums[right] % 2 == 0:
right -= 1
if left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
1.5 Pivot Sort
需求: 已知 pivot 值，把目标数组 nums 中所有小于 pivot 的元素都排在大于 pivot 的元素左侧
nums = [9, 7, 6, 3, 1]
pivotSort(nums, 5) >>> [1, 3, 6, 7, 9]
算法本身与 Odd Even Sort 非常类似
def pivotSort(nums, pivot):
left, right = 0, len(nums)-1
while left < right:
while left < right and nums[left] < pivot:
left += 1
while left < right and nums[right] > pivot:
right -= 1
if left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
1.6 Remove Element
需求: 已知 val 值，去除目标数组 nums 中所有等于 val 的元素（当然前提是不能使用 del List[i] 等直接删除元素的方法）
nums = [1, 7, 6, 3, 7, 8, 9]
removeElement(nums, 7) >>> [1, 9, 6, 3, 8]
Solution 1: Two Pointers Method
总体结构类似于 Odd Even Sort & Pivot Sort:
- 通过左、右指针与 val 值的比较，把所有等于 val 的元素移动到其他不等于 val 的元素的右边
- 然后返回左半边数组
def removeElement(nums, val):
left, right = 0, len(nums)-1
while left <= right:
while left <= right and nums[left] != val:
left += 1
while left <= right and nums[right] == val:
right -= 1
if left <= right: # 此时 nums[left]==val, nums[right]!=val
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums[:left]
Solution 2
相较于 Two Pointers Method 中的替换操作，该方法使用了覆盖操作:
- 使用 index 指针从左至右遍历，如果遍历到等于 val 的元素，就从数组右端取一个元素覆盖
- 然后返回左半边数组
def removeElement(nums, val):
index, length = 0, len(nums)
while index < length:
if nums[index] != val:
index += 1
else:
length -= 1
nums[index] = nums[length]
return nums[:index]
1.6 Merge Sorted Array
Two Pointers Method 应用于一个数组时往往指一左一右两个指针，而应用于多个数组时则指各个数组的左指针
需求: 按升序合并两个升序排列的数组
l1 = [1, 3, 4, 9]
l2 = [2, 5, 7]
mergeTwoLists(l1, l2) >>> [1, 2, 3, 4, 5, 7, 9]
def mergeTwoLists(l1, l2):
p1, p2 = 0, 0
result = []
while p1 < len(l1) and p2 < len(l2):
if l1[p1] < l2[p2]:
result.append(l1[p1])
p1 += 1
else:
result.append(l2[p2])
p2 += 1
while p1 < len(l1):
result.append(l1[p1])
p1 += 1
while p2 < len(l2):
result.append(l2[p2])
p2 += 1
return result
2. Binary Search
2.1 Binary Search
相较于 Two Pointers Method（两个指针所指向的元素用于直接和目标进行比较），二分搜索中的左右指针用于确定搜索对象的范围 (upper & lower bounds)
此外，二分搜索还引入了 mid pointer 用于与和搜索对象进行比较，从而用于调整下次搜索的范围(Update upper or lower bounds): mid = (left + right) // 2
实现效果:
nums = [1, 2, 3, 4, 5, 7, 9]
BinarySearch(nums, 7) >>> 5
def BinarySearch(nums, target):
# 默认输入 nums 为升序排列
left, right = 0, len(nums)-1
while left <= right:
mid = (left + right)//2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
# Why not right = mid? 因为左右指针的核心是[范围]
# 如果 mid > target，那么右边界就变成了 mid - 1
elif nums[mid] < target:
left = mid + 1
return -1
NOTEs: 如何确定 while 循环结束的条件 以二分查找为例，我们纠结的点在于是用 left < right 还是 left <= right，因此我们需要考虑当 left == right 时该结束循环还是继续运行
很简单，因为我们每次比较的都是 mid，也就是说每轮循环开始的left, right 都没有和 target 比较过。因此当 left == right 时循环不能结束
2.2 Search Insert
需求: 在升序数列中查找目标数值的 index，如果没查到，则输出目标数值的插入位置（即返回数组中大于目标数值的最小元素的 index）
nums = [1, 3, 5, 7]
searchInsert(nums, 5) >>> 2
searchInsert(nums, 0) >>> 0
searchInsert(nums, 6) >>> 3
searchInsert(nums, 9) >>> 4
def searchInsert(nums, target):
left, right = 0, len(nums)-1
while left < right:
mid = (left + right)//2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid + 1
return right if nums[right] > target else right+1
相较于 Binary Search，该算法最核心的变化在于更新 right 指针的方式: 把第八行原先的 right = mid - 1 >>> right = mid
这是因为当找不到等于 target 的元素时，我们需要通过 right 来返回数组中大于 target 的最小元素，而 right = mid - 1 则可能使其指向元素小于 target
函数末尾 return right 后跟了一个条件语句，这是为了应对当 target 大于数组中的所有元素这一情况
NOTEs: 如何确定 while 循环结束的条件 我们需要考虑当 left == right 时该结束循环还是继续运行。此时 mid = left = right, 因此 nums[mid] = nums[right] > target, 结合第7、8两行代码即会使得 while 无限循环，因此取 < instead of <=
2.3 Search in Rotated Sorted Array
For a sorted array [0 1 2 3 4], it’s rotated sorted array could be
[4 0 1 2 3][3 4 0 1 2][2 3 4 0 1][1 2 3 4 0]
不难发现对于 rotated sorted array，在经过切分之后，会变成一个 rotated sorted array + 一个 sorted array，例如 [4 0 1 2 3] $\to$ [4 0 1] + [1 2 3]。因此
- 如果目标值处于切分后的 sorted array 中，直接 binary search
- 如果目标值处于切分后的 rotated sorted array 中，我们没有直接的查找方法，此时需要对这个切分后的 rotated sorted array 进行进一步的切分，直至找到目标值 index
def BinarySort(nums, target):
left, right = 0, len(nums)-1
while left <= right:
mid = left + (right-left)//2
if nums[mid] == target:
return mid
# case 1: [2 3 4 0 1]
if nums[left] <= nums[mid]:
# if target in the sorted part
if nums[left] <= target and target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# case 2: [3 4 0 1 2]
else:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
NOTEs: `<` OR `<=`?
- 从小到大来看，首先是第9行，因为
nums[mid]已经和target比较过了，而nums[left]没有，因此一个取小于等于一个取小于，第16行同理 - 再是第8行，当
nums[left] == nums[mid]，此时说明right = left + 1，也就是只剩下nums[right]没有和target比较过，而当取等号时，其后代码(10-13)能够实现这个比较 - 最后是第一行，当
left == right，此时毫无疑问有比较的意义，取等号
Document Information
- Author: Zeka Lee
- Link: https://zhekaili.github.io/0011/04/01/(Py)Array/
- Copyright: 自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）