原題
給出一個整數(shù)數(shù)組nums和一個整數(shù)k揣钦。劃分?jǐn)?shù)組（即移動數(shù)組nums中的元素）矩乐，使得：
所有小于k的元素移到左邊
所有大于等于k的元素移到右邊
返回數(shù)組劃分的位置，即數(shù)組中第一個位置i，滿足nums[i]大于等于k九杂。
給出數(shù)組nums=[3,2,2,1]和 k=2施禾，返回 1
解題思路
- 非常相似的題[Partition Array by Odd and Even]
- 正宗兩個指針中對撞型指針的問題
- 最外層大while循環(huán)脚线，終止條件是兩根指針對撞
- 內(nèi)層循環(huán)，分三步走
- 左邊如果小于K, left++
- 右邊如果大于等于K, right--
- 最后停下時如果left <= right, swap
完整代碼
class Solution:
"""
@param nums: The integer array you should partition
@param k: As description
@return: The index after partition
"""
def partitionArray(self, nums, k):
# write your code here
# you should partition the nums by k
# and return the partition index as description
if not nums:
return 0
left, right = 0, len(nums) - 1
while left <= right:
while left <= right and nums[left] < k:
left += 1
while left <= right and nums[right] >= k:
right -= 1
if left <= right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return left
