Partition Array

Given an arraynumsof integers and an intk, 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 indexi_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 innums_are smaller than_k, then returnnums.length

Example

If nums =[3,2,2,1]andk=2, a valid answer is1.

分析

对撞型指针,只需要把数移到K左右两边，无需排序，所以没有递归。

答案：

public class Solution {
    /** 
     *@param nums: The integer array you should partition
     *@param k: As description
     *return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
        //write your code here
        int l=nums.length;
        if(l==0)
        return 0;
        int start=0, end=l-1;

        while(start<=end){
//把>=都换到右边
            while(start<=end && nums[start]<k){
                start++;
            }

           while(start<=end && nums[end]>=k){
                end--;
           }
//把<换到左边                
           if(start<=end){
               int temp=nums[start];
               nums[start]=nums[end];
               nums[end]=temp;

               start++;
                end--;
           }
        }
            return start;
    }
}