题目

WeChatea5a569331940133f51104f88b79f4e2.png

题目要求

直接在nums上排序，不用新的memory，且不使用自带的sort function

解题思路（多指针）

此题为 Dutch national flag problem，使用了三指针i, j, k。其含义和逻辑见代码注释和下图
WeChatf289994f9fa5c9783954a30d0acac1a7.png

  1. class Solution:
  2.     def sortColors(self, nums: List[int]) -> None:
  3.         # i, index ready to swap where nums[i]<mid is expected at this index
  4.         # j, current index where nums[j]=mid is expected, if not, swap with index i or index k accordingly
  5.         # k, index ready tp swap where nums[k]>mid is expected at this index
  6.         i = 0
  7.         j = 0
  8.         k = len(nums) - 1
  9.         mid = 1
  10.         while j<=k:
  11.             if nums[j] < mid: # swap with index i
  12.                 nums[i], nums[j] = nums[j], nums[i]
  13.                 i += 1
  14.                 j += 1
  15.             elif nums[j] > mid: #swap with index k
  16.                 # j,k has swapped, we need to consider the new nums[j] 
  17.                 # so we don't need to do j += 1 here
  18.                 nums[j], nums[k] = nums[k], nums[j]
  19.                 k -= 1
  20.             else:
  21.                 j += 1

为什么 swap i, j需要 j+= 1, 而swap j,k 确不需要？

通过下面两个例子我们来观察一下i, j, k的变化，以及发现为什么 while j<=k作为循环条件。
当4->5时，首先明白调换之后，新的位置j已经变了，对于这个数我们要重新考量排序, 因此swap(j,k)之后，不应该执行j+=1。其次，到达第5步时，很显然排序并没有结束，所以循环条件是while j<=k而不是while j<k

WeChat19192181ae328506de7b9d0c6e2c86bf.pngWeChateccbe529bad1c46259a296b93f632ae8.png