# coding = utf-8
'''
Created on 2015年11月10日
@author: SphinxW
'''
# 数组划分
#
# 给出一个整数数组nums和一个整数k。划分数组（即移动数组nums中的元素），使得：
#
# 所有小于k的元素移到左边
# 所有大于等于k的元素移到右边
#
# 返回数组划分的位置，即数组中第一个位置i，满足nums[i]大于等于k。
# 样例
#
# 给出数组nums=[3,2,2,1]和 k=2，返回 1
# 注意
#
# 你应该真正的划分数组nums，而不仅仅只是计算比k小的整数数，如果数组nums中的所有元素都比k小，则返回nums.length。
# 挑战
#
# 要求在原地使用O(n)的时间复杂度来划分数组
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
headIndex = 0
count = 0
count2 = 0
if len(nums) == 0:
return 0
while headIndex + count2 < len(nums):
print(nums)
head = nums[headIndex]
if head == k:
headIndex += 1
count += 1
elif head < k:
del nums[headIndex]
nums.insert(0, head)
headIndex += 1
else:
count2 += 1
del nums[headIndex]
nums.append(head)
return headIndex - count
LintCode_chapter2_section10_partition-array
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
