[LintCode] 625 Partition Array II 解题报告

Description
Partition an unsorted integer array into three parts:

The front part < low
The middle part >= low & <= high
The tail part > high
Return any of the possible solutions.


Notice
low <= high in all testcases.



Example
Given [4,3,4,1,2,3,1,2], and low = 2 and high = 3.

Change to [1,1,2,3,2,3,4,4].

([1,1,2,2,3,3,4,4] is also a correct answer, but [1,2,1,2,3,3,4,4] is not)



Challenge
Do it in place.
Do it in one pass (one loop).



思路
标准的3-way-partition。判断的时候不是只有一个v，而是有low和high而已。



Code

public class Solution {
    /**
     * @param nums an integer array
     * @param low an integer
     * @param high an integer
     * @return nothing
     */
    public void partition2(int[] nums, int low, int high) {
        // Write your code here
        
        int lt = 0;
        int gt = nums.length - 1;
        int i = 0;
        while (i <= gt) {
            if (nums[i] < low) {
                exch(nums, lt++, i++);
            }
            else if (nums[i] > high) {
                exch(nums, i, gt--);
            }
            else {
                i++;
            }
        }
    }
    
    public void exch(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}