[数据结构与算法]leetcode215对官方题解做的一些改进堆排序(100％)快排

题目描述:

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

?方法1:小顶堆

官方题解为建立小顶堆,再一个个删除,剩下k个数,堆顶即为答案.

改进一下,利用前k个数创建小顶堆,如果有大于堆顶的后续数,则替换并调整堆

class Solution {
private:
    vector<int> v;
    int n;
    void adjheap(int i)
    {
        int left = i * 2 + 1, right = i * 2 + 2, indx = i;
        // 找当前节点和左右子节点中最大的
        if(left < n && v[indx] > v[left])
        {
            indx = left;
        }
        if(right < n && v[indx] > v[right])
        {
            indx = right;
        }
        // 如果最大的为子节点,交换,再递归
        if(indx != i)
        {
            swap(v[i], v[indx]);
            adjheap(indx);
        }
    }
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        v.assign(nums.begin(), nums.begin() + k);
        n = k;
        int size = nums.size();
        // 前k个数建立小顶堆
        for(int i=k/2; i>=0; --i)
        {
            adjheap(i);
        }
        // 后续数字,大于七个中最小的,加入,重新调整堆
        for(int i=k; i<size; ++i)
        {
            if(nums[i] > v[0])
            {
                v[0] = nums[i];
                adjheap(0);
            }
        }
        return v[0];
    }
};

方法2:快排

左右标签同时向内,需要注意的细节就是哪个标签先越界的

class Solution {
private:
    vector<int> v;
    int partition(int left, int right)
    {
        int tag = v[left];
        int begin = left;
        while(left < right)
        {
            while(left < right && v[right] >= tag) right--;    // right先越界
            while(left < right && v[left] <= tag) left++;
            if(left < right)
            {
                swap(v[left], v[right]);
            }
        }
        swap(v[begin], v[right]);    // 所以要交换right
        return right;
    }
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        v = nums;
        int n = nums.size();
        int tag = n - k;
        int left = 0, right = n - 1;
        while(true)
        {
            int indx;
            indx = partition(left, right);
            if(indx < tag)
            {
                left = indx + 1;
            }
            else if(indx > tag)
            {
                right = indx - 1;
            }
            else
            {
                return v[indx];
            }
        }
    }
};