75. Sort Colors
题目要求见： https://leetcode.com/problems/sort-colors/
方法一
two-pass方法，先遍历一遍，记下0, 1, 2元素的数目；再遍历一遍，分别将这些数目的0, 1, 2覆盖nums.
时间复杂度：O(n)
空间复杂度：O(1)
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
#method1
if not nums:
return
count = [0,0,0]
for ele in nums:
if ele == 0:
count[0]+=1
elif ele == 1:
count[1] +=1
elif ele ==2:
count[2] +=1
else:
return
p = 0
while count[0]>0:
nums[p] = 0
p+=1
count[0] -=1
while count[1] > 0:
nums[p] = 1
p += 1
count[1] -= 1
while count[2] > 0:
nums[p] = 2
p += 1
count[2] -= 1
方法二
维护三个指针，p0, p1, p2.
- p0: [0, p0] 为０
- p1: (p0, p1] 为１
- p2: [p2, n) 为２
时间复杂度：O(n)
空间复杂度：O(1)
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
#method2
if not nums:
return
n = len(nums)
p0 = -1 #[0, p0]
p1 = 0 # start from 0, meaning (p0, p1] is 1
p2 = n # [p2, n) is 2
while p1 < p2:
if nums[p1] ==1:
p1+=1
elif nums[p1] ==0:
p0+=1
temp = nums[p1]
nums[p1] = nums[p0]
nums[p0] = temp
p1 +=1
elif nums[p1] ==2:
#swap
p2 -=1
nums[p1], nums[p2] = nums[p2], nums[p1]
88. Merge Sorted Array
题目要求见： https://leetcode.com/problems/merge-sorted-array/
如果nums2为空，直接返回nums1；如果nums2都比nums1大，直接整体移到nums1后面；如果nums2都比nums1小，把nums1整体后移，再把nums2整体拼接到nums1前面．
如果nums1, nums2范围有交集，就维持两个指针指向nums1, nums2的尾部，每次把更大的值赋值给nums1尾部，然后该值的指针前移．
如果最后剩下了nums2的指针，就直接把剩下部分的数拼接到nums1的头部．
时间复杂度：O(n)
空间复杂度：O(1)
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
if not nums2:
return
if nums1 and nums2:
if nums2[0] >= nums1[m-1]:
nums1[m:m+n] = nums2[:]
elif nums2[-1] <= nums1[0]:
nums1[n:n+m] = nums1[:m]
nums1[:n] = nums2[:]
else:
p1, p2 = m, n
while m and n:
if 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
if n:
nums1[:n] = nums2[:n]
这里有一个Python的陷阱：当ｎ变成０的时候，再循环下去就是 -1，于是从nums2第一个元素指向了nums2最后一个元素．所以必须要以０为边界条件，然后再另加判断．
215. Kth Largest Element in an Array
题目要求见： https://leetcode.com/problems/kth-largest-element-in-an-array/
方法一
最傻的办法是 快速排序+切片取第ｋ个值．这里手动实现快速排序作为练习．
时间复杂度：O(nlogn)
空间复杂度：O(1)
class Solution(object):
def findKthLargest(self, nums, k):
def quicksort(array,low,high):
''' realize from book "data struct" of author 严蔚敏
'''
if low < high:
key_index = partion(array,low,high)
quicksort(array,low,key_index)
quicksort(array,key_index+1,high)
def partion(array,low,high):
key = array[low]
while low < high:
while low < high and array[high] >= key:
high -= 1
if low < high:
array[low] = array[high]
while low < high and array[low] < key:
low += 1
if low < high:
array[high] = array[low]
array[low] = key
return low
if not nums:
return
n = len(nums)
quicksort(nums, 0, n-1)
return nums[-k]
方法二 改良的快速排序
快速排序是递归地在一个范围内选取pivot，然后把小于pivot的数移到其左边，大于pivot的数移到其右边，然后再对左右两个更小的范围进行排序．
因为每次排序完后，pivot的位置刚好对应其排序的位置，所以可利用这点决定目标是在左边子范围还是在右边子范围，从而把时间复杂度缩小．
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def partition(left, right, pivot_index):
pivot = nums[pivot_index]
# 1. move pivot to end
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
# 2. move all smaller elements to the left
store_index = left
for i in range(left, right):
if nums[i] < pivot:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
# 3. move pivot to its final place
nums[right], nums[store_index] = nums[store_index], nums[right]
return store_index
def select(left, right, k_smallest):
"""
Returns the k-th smallest element of list within left..right
"""
if left == right: # If the list contains only one element,
return nums[left] # return that element
# select a random pivot_index between
pivot_index = random.randint(left, right)
# find the pivot position in a sorted list
pivot_index = partition(left, right, pivot_index)
# the pivot is in its final sorted position
if k_smallest == pivot_index:
return nums[k_smallest]
# go left
elif k_smallest < pivot_index:
return select(left, pivot_index - 1, k_smallest)
# go right
else:
return select(pivot_index + 1, right, k_smallest)
# kth largest is (n - k)th smallest
return select(0, len(nums) - 1, len(nums) - k)
网友评论