【快排算法】颜色分类 / 排序数组 / 数组中的第K个最大元素 / LCR 库存管理 III

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int i = 0, l = -1, r = nums.size();
        while (i < r)
        {
            if (nums[i] == 0) swap(nums[++l], nums[i++]);
            else if (nums[i] == 1) i++;
            else swap(nums[--r], nums[i]);
        }
    }
};

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(nullptr));
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }
    void qsort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;
        int key = nums[rand() % (r - l + 1) + l]; // 获取随机基准值
        int i = l, left = l - 1, right = r + 1;
        // 三路划分
        while (i < right)
        {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }
        qsort(nums, l, left);
        qsort(nums, right, r);
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for (auto e : nums) pq.push(e);
        int ret = 0;
        while (k--)
        {
            ret = pq.top();
            pq.pop();
        }
        return ret;
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(nullptr));
        return qsort(nums, 0, nums.size() - 1, k);
    }
    int qsort(vector<int>& arr, int l, int r, int k)
    {
        if (l >= r) return arr[l];
        int key = arr[rand() % (r - l + 1) + l]; // 随机基准值
        int i = l, left = l - 1, right = r + 1;
        // 三路划分
        while (i < right)
        {
            if (arr[i] < key) swap(arr[++left], arr[i++]);
            else if (arr[i] == key) i++;
            else swap(arr[--right], arr[i]);
        }
        // 分情况讨论
        int c = r - right + 1, b = right - left - 1;
        if (c >= k) return qsort(arr, right, r, k);
        else if (c + b >= k) return key;
        else return qsort(arr, l, left, k - b - c);
    }
};

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto e : stock) pq.push(e);
        vector<int> ret;
        while (cnt--)
        {
            ret.push_back(pq.top());
            pq.pop();
        }
        return ret;
    }
};

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