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 returnnums.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)?

Tags

Sort Two Pointers Array

2.Code

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;
    }