本文共 1102 字，大约阅读时间需要 3 分钟。

题目地址：

给定一个数组，再给定一个数$k$，要求将数组重排，使得存在某个位置$x$，其前的数都是小于$k$的，其与其后的数都是大于等于$k$的。

直接套用快排的模板即可。需要注意的是由于最后要返回位置$x$，我们还需要判断一下快排完成后的pivot是不是第一个大于等于$k$的位置。代码如下：

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 i = 0, j = nums.length - 1;        int tmp = nums[j];        while (i < j) {               while (i < j && nums[i] < k) {                   i++;            }            nums[j] = nums[i];            while (i < j && nums[j] >= k) {                   j--;            }            nums[i] = nums[j];        }        // 将pivot放回去        nums[i] = tmp;        // 此时i左边的数已经都小于k，i右边的数已经都大于等于k了        // 所以如果nums[i]大于等于k，那么nums[i]就是第一个大于等于k的数；        // 否则或者nums[i + 1]是第一个大于等于k的数，或者大于等于k的数不存在，这两者都返回i + 1        return tmp >= k ? i : i + 1;    }}

时间复杂度$O(n)$，空间$O(1)$。