倉庫管理員以數組?stock?形式記錄商品庫存表，其中?stock[i]?表示對應商品庫存余量。請返回庫存余量最少的?cnt?個商品余量，返回?順序不限。
示例 1：
輸入：stock = [2,5,7,4], cnt = 1 輸出：[2]
示例 2：
輸入：stock = [0,2,3,6], cnt = 2 輸出：[0,2] 或 [2,0]
LCR 159. 庫存管理 III - 力扣（LeetCode）
首先考慮用TreeSet來實現這個代碼，因為TreeSet會基于紅黑樹自動幫我們排序。
class Solution {public int[] inventoryManagement(int[] stock, int cnt) {TreeSet<Integer> treeSet = new TreeSet<>();for(int i = 0; i < stock.length; i++){treeSet.add(stock[i]);}// 取出最小的 cnt 個元素int[] result = new int[cnt];int index = 0;for (int num : treeSet) {if (index < cnt) {result[index++] = num;} else {break; // 已經取夠 cnt 個元素，退出循環}}return result;}
}很明顯，不合適，因為Set集合會去重。
下面改用快排，快排的時間復雜度為O(n)，剛好復習一下快排的代碼。
class Solution {public int[] inventoryManagement(int[] stock, int cnt) {quickSort(stock, 0, stock.length - 1);int[] result = new int[cnt];for(int i = 0; i < cnt; i++){result[i] = stock[i];}return result;}public void quickSort(int[] stock, int low, int high){if (low < high) {// 找到分區點int partitionIndex = partition(stock, low, high);// 遞歸排序左半部分quickSort(stock, low, partitionIndex - 1);// 遞歸排序右半部分quickSort(stock, partitionIndex + 1, high);}}public int partition(int[] stock, int low, int high){//找到基準元素int pivot = stock[low];int left = low + 1; //左指針int right = high; //右指針while(left <= right){while(left <= right && stock[right] > pivot){right--;}while(left <= right && stock[left] < pivot){left++;}if(left <= right){swap(stock,left,right);left++;right--;}}swap(stock,right,low);return right;}private void swap(int[] stock, int i, int j) {int temp = stock[i];stock[i] = stock[j];stock[j] = temp;}}快排的核心全在partition算法里，本質是確定分區點，每一次分區就代表這個元素被排好了。
我們分析一下改怎么寫，如何確定最后return的是左邊還是右邊。
我們把最左端定為哨兵，也就是說最后的位置左邊必須比哨兵小，右邊必須比哨兵大。while循環的條件是left<=right。首先收縮邊界，然后交換，最后的情況是right指著最后一個小于或等于?pivot?的元素。因此要pivot和right換。
