Partition Array

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.
其实就是quicksort的第一步，

public class Solution {
    /**
     * @param nums: The integer array you should partition
     * @param k: An integer
     * @return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {
        int start = 0;
        int end = nums.length - 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;
    }
}

这个题也可用sort color的思路处理。

    public int partitionArray(int[] nums, int k) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            if (nums[start] < k) {
                start++;
            } else {
                int temp = nums[end];
                nums[end] = nums[start];
                nums[start] = temp;
                end--;
            }
        }
        return start;
    }

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) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return partition(nums, 0, nums.length - 1, k);
    }

    public void swap(int[] nums, int x, int y){
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }

    public int partition(int[] nums, int start, int end, int pivot) {
        int low = start;
        int high = end;
        while (low <= high) {
            while(low <= high && nums[low] < pivot) {
                low++;
            }
            while(low <= high && nums[high] >= pivot) {
                high--;
            }

            if (low <= high) {
                swap(nums, low, high);
                low++;
                high--;
            }
        }
        return low;
        //return high + 1;
    }   
}