python - Partition Array

Question

Given an array nums of integers and an int k, partition the array (i.e move the elements in nums) such that: All elements < k are moved to the left. All elements >= k are moved to the right Return the partitioning index, i.e the first index i nums[i] >= k.

class Solution:
    def partitionArray(self, nums, k):
        # write your code here
        if nums == []:
            return 0
        left = 0
        i = 0
        while i <= len(nums):
            if nums[i] < k:
                i += 1
                left += 1
            else:
                r = nums[i]
                del nums[i]
                nums.append(r)
                i += 1

        return left

My idea is to going through the list one by one. The num[i] whose larger than k will be removed and append at the end of the num, the one whose smaller than k will be kept at the original place. Once the whole list has been going through, all the smaller num are at the front. left is a counter at this point for return. But I cannot fix the problem with nums[i]. After the each mods to the list, the counter i cannot point at the correct item in the list.

How can I write the code base on this idea???

Answer 1

You're looking for the index(k). This seems like a homework assignment so you may be limited to what built in functionality you can use. However, a pythonic approach to this is

def solution(nums, k):
    return sorted(nums).index(k)

You are doing several things I would recommend avoiding.

1. Concurrent modification; you should not add or delete from a list while looping it.
2. You can not loop up to i == len(nums) because list indexes start at 0.

Since you are really just looking for index(k) you need only keep track of numbers less than k and not concern yourself with re-organizing the list.

class Solution:
    def partitionArray(self,nums, k):
        # write your code here
        if nums == []:
            return 0
        left = 0
        i = 0
        while i < len(nums):
            if nums[i] < k:
                left += 1
            i += 1

        return left