LintCode Q31 Partition Array in Python

  • Jinhai ZHOU
  • 3 Minutes
  • 2016年12月20日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
lo = 0
hi = len(nums) - 1
# when no item in nums
if hi == -1:
return 0
while lo < hi:
while lo < hi and nums[lo] < k:
lo += 1
while lo < hi and nums[hi] >= k:
hi -= 1
if lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
for i in xrange(len(nums)):
if nums[i] >= k:
return i
return len(nums)
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。