31.Partition Array

1.Description(Medium)

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 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 innums are smaller than k, then return nums.length

Example

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

Challenge

Can you partition the array in-place and in O(n)?

2.Code

经典的partition做法，quicksort的一部分

关于left<=right 而不是left<right:

在partition array这道题中,如果所有的数字都小于k的话, 你使用<符号,它并没有考虑到数组的最后一个数字.

 public int partitionArray(int[] nums, int k) {
        if(nums==null || nums.length==0){
            return 0;
        }
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            //注意这两个while里面都要加上ledt<=right 否则会出现java.lang.ArrayIndexOutOfBoundsException
            while(left<=right && nums[left]<k){
                left++;
            }
            while(left<=right && nums[right]>=k){
                right--;
            }
            if(left<=right){
                int temp=nums[left];
                nums[left]=nums[right];
                nums[right]=temp;
                left++;
                right--;
            }
        }
        return left;
    }