LintCode_chapter2_section10_part

# 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