> 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/31partition-array.md).

# 31.Partition Array

## 1.Description(Medium)

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*.

### 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]`and`k=2`, a valid answer is`1`.

[**Challenge**](https://www.lintcode.com/en/problem/partition-array/#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;
    }
```