> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/7.two-pointers/625partition-array-ii.md).

# 625.Partition Array II

## 1.Description(Medium)

Partition an unsorted integer array into three parts:

1. The front part < *low*
2. The middle part >= *low* & <= *high3.*

   3.The tail part > *high*

Return any of the possible solutions.

### Notice

low <= high in all test cases.

**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**](https://www.lintcode.com/en/problem/partition-array-ii/#challenge)

1. Do it in place.
2. Do it in one pass (one loop).

## 2.Code

跟sort colors II 非常相似，只不过sort color II 里面的上下限需要不断变化，这个题目是固定的low high

在代码里的变化就是sort colors II 在while(i<=right)外层还有一个while(min\<max)的一层，在这一层里，控制最后结束时i要变回当前left的位置，以及min 和max的变化。

```
 public void partition2(int[] nums, int low, int high) {
        if(nums==null || nums.length==0){
            return;
        }
        int left=0;
        int right=nums.length-1;
        int i=0;
        while(i<=right){
            if(nums[i]<low){
                swap(nums,i,left);
                i++;
                left++;               
            }
            else if(nums[i]>high){
                swap(nums,i,right);
                right--;
            }else{
                i++;
            }
        }
    }

    public void swap(int[] colors,int i,int j){
        int temp=colors[i];
        colors[i]=colors[j];
        colors[j]=temp;
    }
```