目錄

1、75. 顏色分類

2、912. 排序數組

3、?215. 數組中的第K個最大元素

4、LCR 159. 庫存管理 III

---

1、75. 顏色分類

?思路：利用快速排序思路，使用三指針分塊進行優化。

• [0,left]——小于key
• [left+1,right-1]——等于key
• [right,nums.size()]——大于key

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int left = -1, right = n, cur = 0;while (cur < right) {if (nums[cur] == 0)swap(nums[++left], nums[cur++]);else if (nums[cur] == 2)swap(nums[--right], nums[cur]);elsecur++;}}
};

2、912. 排序數組

?

思路：快排+三指針優化+隨機選擇基準元素

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL));qsort(nums,0,nums.size()-1);return nums;}int getRandom(vector<int>& nums,int left,int right){int i=rand();return nums[i%(right-left+1)+left];}void qsort(vector<int>& nums,int begin,int end){if(begin >= end)return;int i=begin,left=begin-1,right=end+1;int key=getRandom(nums,begin,end);while(i<right){if(nums[i]<key)swap(nums[++left],nums[i++]);else if(nums[i]>key)swap(nums[--right],nums[i]);elsei++;}qsort(nums,begin,left);qsort(nums,right,end);}
};

3、?215. 數組中的第K個最大元素

思路：快速選擇（快排+三指針分塊+隨機選擇基準元素+遞歸排序時進入對應區間）

• 第k個最大元素也就是排序(升序)后的倒數第k個

? ? ?<key? ? ? ? ? ? ? ?=key? ? ? ? ? ? ? ? >key
|————|————————|—————|

l? ? ? ? ? left left+1? ? ? ? right-1 right? ? ? ? ? ? ?r

? ? ? ? a? ? ? ? ? ? ? ? ? ? b? ? ? ? ? ? ? ? ? ? ? ? c（區間元素個數）

c表示在當前key（基準值）右側的元素數量（即比key大的元素數量），b表示等于key的元素數量。由于我們是尋找第k個最大的元素，數組的右側代表了較大的元素。

• if (c >= k)：如果key右側的元素數量c大于或等于k，這意味著第k個最大的元素位于key的右側或者是key本身。因此，我們遞歸地在key右側的數組部分繼續進行快速選擇，尋找第k個最大的元素。

• else if (b + c >= k)：如果key右側的元素數量c加上等于key的元素數量b大于或等于k，這意味著第k個最大的元素要么是key本身，要么在等于key的這些元素中。由于這些元素都是相等的，我們可以直接返回key作為第k個最大的元素。

• else：如果上述兩個條件都不滿足，這意味著第k個最大的元素位于key的左側。因此，我們遞歸地在pivot左側的數組部分繼續進行快速選擇。此時，我們需要調整k的值，因為我們已經排除了b + c個比key大或等于key的元素，所以新的k應該減去這部分已經排除的元素數量。

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}int qsort(vector<int>& nums, int l, int r, int k) {if (l == r)return nums[l];int key = getRandom(nums, l, r);int left = l - 1, right = r + 1, i = l;while (i < right) {if (nums[i] < key)swap(nums[++left], nums[i++]);else if (nums[i] > key)swap(nums[--right], nums[i]);elsei++;}int c = r - right + 1, b = right - left - 1;if (c >= k)return qsort(nums, right, r, k);else if (b + c >= k)return key;elsereturn qsort(nums, l, left, k - b - c);}int getRandom(vector<int>& nums, int left, int right) {return nums[rand() % (right - left + 1) + left];}
};

?為了找到數組中第k個最大的元素，并且要求時間復雜度為O(n)，我們可以比較這些方法：

1. 快速選擇算法（第一種方法）:

   • 優點: 平均時間復雜度為O(n)，符合題目要求。它通過隨機選擇一個樞軸來分割數組，然后只在包含第k個最大元素的那部分數組上遞歸，從而減少了不必要的計算。
   • 缺點: 最壞情況下的時間復雜度為O(n^2)，但這種情況很少發生。算法的性能依賴于隨機數的選擇。

2. 最小堆（第二種方法）:

   • 優點: 對于找到第k個最大元素，這種方法維護了一個大小為k的最小堆，時間復雜度為O(n log k)，適合k遠小于n的情況。
   • 缺點: 當k接近n時，性能不如快速選擇算法。

     class Solution {
     public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k);for(size_t i=k;i<nums.size();i++){if(nums[i]>pq.top()){pq.pop();pq.push(nums[i]);}}return pq.top();}
     };

3. 排序（第三種方法）:

   • 優點: 實現簡單，直觀易懂。
   • 缺點: 時間復雜度為O(n log n)，不滿足題目對O(n)時間復雜度的要求。

     class Solution {
     public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(),nums.end());return nums[nums.size()-k];}
     };

4. 最大堆（第四種方法）:

   • 優點: 通過構建一個最大堆，然后彈出k-1次，可以直接得到第k個最大元素。這種方法簡單且對于理解堆結構很有幫助。
   • 缺點: 時間復雜度為O(n + k log n)，當k較小相對高效，但當k接近n時，性能下降。

     class Solution {
     public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int> pq(nums.begin(),nums.end());while(--k){pq.pop();}return pq.top();}
     };

結論:

• 如果你追求平均情況下的最優時間復雜度，并且可以接受在極少數情況下性能的不確定性，快速選擇算法是最佳選擇。
• 如果k值較小，最小堆方法也是一個不錯的選擇，因為它可以較快地找到第k個最大的元素。
• 排序方法雖然簡單，但不滿足題目對時間復雜度的要求。
• 最大堆方法適用于k值較小的情況，但當k值較大時，性能不是最優的。

綜上所述，考慮到時間復雜度的要求和算法的效率，快速選擇算法是最符合題目要求的解決方案

4、LCR 159. 庫存管理 III

思路：快速選擇（快排+三指針分塊+隨機選擇基準元素+進入對應區間尋找）
? ? ?<key? ? ? ? ? ? ? ?=key? ? ? ? ? ? ? ? >key
|————|————————|—————|

l? ? ? ? ? left left+1? ? ? ? right-1 right? ? ? ? ? ? ?r

? ? ? ? a? ? ? ? ? ? ? ? ? ? b? ? ? ? ? ? ? ? ? ? ? ? c（區間元素個數）

a表示在當前的key（基準值）左邊的元素數量，b表示等于key的元素數量。cnt是我們需要找到的庫存余量最少的商品數量。

• if (a > cnt)：如果key左邊的元素數量a大于cnt，這意味著我們需要的cnt個最小元素全部位于key的左邊。因此，我們遞歸地在key左邊的數組部分繼續進行快速選擇，尋找這cnt個最小元素。

• else if (a + b >= cnt)：如果key左邊的元素數量a加上等于key的元素數量b大于或等于cnt，這意味著我們需要的cnt個最小元素已經包含在左邊的元素和等于key的元素中。由于題目說明返回順序不限，我們不需要進一步排序或選擇，可以直接返回結果。

• else：如果上述兩個條件都不滿足，這意味著我們需要的cnt個最小元素部分位于key的右邊。因此，我們遞歸地在key右邊的數組部分繼續進行快速選擇。此時，我們需要調整cnt的值，因為我們已經找到了一部分所需的最小元素（即a + b個），所以新的cnt應該減去這部分已經找到的元素數量。

class Solution {
public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(NULL));qsort(stock, 0, stock.size() - 1, cnt);return {stock.begin(), stock.begin() + cnt};}int qsort(vector<int>& stock, int l, int r, int cnt) {if (l == r)return stock[l];int key = getRandom(stock, l, r);int left = l - 1, right = r + 1, i = l;while (i < right) {if (stock[i] < key)swap(stock[++left], stock[i++]);else if (stock[i] > key)swap(stock[--right], stock[i]);elsei++;}int a = left - l + 1, b = right - left - 1;if (a > cnt)return qsort(stock, l, left, cnt);else if (a + b >= cnt)return 0;elsereturn qsort(stock, right, r, cnt - b - a);}int getRandom(vector<int>& stock, int left, int right) {return stock[rand() % (right - left + 1) + left];}
};