Lintcode31 Partition Array solution problem solution

[topic description]

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.

Notice:You should do really partition in array nums instead of just counting the numbers of integers smaller than k.If all elements in nums are smaller than k, then return nums.length

An array of integers nums and an integer k are given. Partition the array (that is, move the elements in the array nums) so that: all elements less than k move to the left; all elements greater than or equal to k move to the right; return the position of the array partition, that is, the first position in the array I, satisfying that nums [I] is greater than or equal to k.

Note: you should actually partition the array nums, not just counting integers smaller than k, and return nums.length if all elements in the array nums are smaller than k.

[topic link]

Http://www.lintcode.com/en/problem/partition-array/

[topic Analysis]

An easy way to think of is to traverse from left to right, using right to save the index greater than or equal to k, and I is the index of the current traversal element, always keeping I > = right, then the final returned right is the result.

Traversing from left to right, when an element less than k is encountered, it is exchanged with the element at the right index, and the self-increasing right points to the next element, which ensures that the element before right must be less than k. Note that in the if judgment condition, I > = right cannot be I > right, otherwise special cases such as all less than k need to be considered, and even if this special case is considered, there may be other bug. What exactly is bug? Welcome to put forward your analysis.

Have known Quick Sort to do this problem is a minute-by-minute thing, using the left and right two pointers left,right represent less than, greater than or equal to k index, start at the same time, until left > right.

The condition for the normal operation of the large cycle is left.