# 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; 
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/array/partition_array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.