算法面试真题详解：数组划分

描述
给出一个整数数组 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;
  }
  }

  更多题解参考：九章官网solution