算法面試真題詳解：數組劃分

描述

給出一個整數數組 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