# Partition Array

`Sort`, `Array`, `Two Pointers`

**Medium** 

## Problem

> 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 in nums are smaller than k, then return nums.length

## Analysis

根据给定的k，也就是类似于Quick Sort中的pivot，将array从两头进行缩进，时间复杂度 O(n)

## Solution

Quick Select

```java
public class Solution {
    private void swap(int i, int j, int[] arr) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    /**
     *@param nums: The integer array you should partition
     *@param k: As description
     *return: The index after partition
     */
    public int partitionArray(int[] nums, int k) {

        int pl = 0;
        int pr = nums.length - 1;
        while (pl <= pr) {
            while (pl <= pr && nums[pl] < k) {
                pl++;
            }
            while (pl <= pr && nums[pr] >= k) {
                pr--;
            }
            if (pl <= pr) {
                swap(pl, pr, nums);
            }
        }
        return pl;
    }
}
```

Another approach: O(n)

设置一个offset值，每次将 \<k 的值与offset位置上的值交换位置，然后offset++。因为不需要担心顺序，所以可以无论exchange的数是否小于k，最后所有左边的数都会小于k

```java
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) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0; 
        }

        int offset = 0; 
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < k) {
                int temp = nums[i];
                nums[i] = nums[offset]; 
                nums[offset] = temp;
                offset ++; 
            }
        }

        return offset; 
    }
}
```