所有小于k的元素移到左边
所有大于等于k的元素移到右边

public class lintCode31 {
    public int partitionArray(int[] nums, int k) {
        if(nums == null || nums.length ==0) return 0;
        int start = 0;
        int end = nums.length -1;
        while(start < end){
            while(nums[end] >= k  && start < end){
                end--;
            }
            while(nums[start] < k && start < end){
                start++;
            }
            if(start < end){
                int tmp = nums[start];
                nums[start] = nums[end];
                nums[end] = tmp;
            }
        }
        if(nums[start] > k){
            return start;
        }else{
            return start+1;
        }
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = new int[]{3,2,2,1};
        int k = 2;
        System.out.println(new lintCode31().partitionArray(nums, k));
    }
}