描述

给出一个整数数组 nums 和一个整数 k 。划分数组（即移动数组 nums 中的元素），使得：

• 所有小于 k 的元素移到左边
• 所有大于等于 k 的元素移到右边

返回数组划分的位置，即数组中第一个位置 i，满足 nums[i] 大于等于 k 。

在线评测地址

样例 1

输入: [],9 输出: 0 

样例 2

输入: [3,2,2,1],2 输出:1 解释: 真实的数组为[1,2,2,3].所以返回 1 

算法：快速选择算法

算法思路

• 通过头尾指针跳过小于 k 的前缀和大于等于 k 的后缀，可以找到与第一个大于等于 k 的值和最后一个小于 k 的值。进行交换后可达到划分数组的目的，直到找到两个指针相遇为止。

• 伪代码如下：

• 令 left = 0，right = length-1 。

• 当 nums[left] < k 时，left 指针向右移动。

• 当 nums[right] >= k 时，right 指针向左移动。

• 如果 left <= right，交换两个值。

• 如果 left > right，返回 left 作为最终结果，否则返回第二步。

复杂度分析

• 设数组长度为 n

• 时间复杂度 O(n)

• 最多扫描一遍数组，时间复杂度为 O(n)

• 空间复杂度 O(1)

• 只需要选择用的游标变量的额外空间，所以空间复杂度为 O(1)

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) {         if (nums == null) {             return 0;         }         int left = 0, right = nums.length - 1;         while (left <= right) {             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;     } } 

更多题解参考

大佬有話說 (0)