【C++算法】分治——快排

颜色分类

• 题目链接

颜色分类https://leetcode.cn/problems/sort-colors/description/

• 算法原理

• 代码步骤

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

排序数组

• 题目链接

排序数组https://leetcode.cn/problems/sort-an-array/description/

• 算法原理

• 代码步骤

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }

    void qsort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;
        int key = getRandom(nums, l, r);
        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);
    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }
};

数组中第k个最大元素

• 题目链接

数组中的第k个最大元素https://leetcode.cn/problems/kth-largest-element-in-an-array/description/

• 算法原理

• 代码步骤

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 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]);
        }

        int c = r - right + 1, b = right - left - 1;
        if(c >= k) return qsort(nums, right, r, k);
        else if(c + b >= k) return key;
        else return qsort(nums, l, left, k - c - b);

    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }
};

库存管理III

• 题目链接

库存管理IIIhttps://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/

• 算法原理

• 代码步骤

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};
    }

    void qsort(vector<int>& stock, int l, int r, int cnt)
    {
        if(l >= r) return;
        int key = getRandom(stock, l, r);
        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(cnt < a) qsort(stock, l, left, cnt);
        else if(cnt <= a + b) return;
        else qsort(stock, right, r, cnt - a - b);
    }

    int getRandom(vector<int>& stock, int left, int right)
    {
        return stock[rand() % (right - left + 1) + left];
    }
};