乐趣区

关于c++:leetcode笔记215-数组中的第K个最大元素

jiezi

题目形容

题目链接：https://leetcode-cn.com/probl…
在未排序的数组中找到第 k 个最大的元素。请留神，你须要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1：
输出: [3,2,1,5,6,4] 和 k = 2
输入: 5
示例 2：
输出: [3,2,3,1,2,4,5,5,6] 和 k = 4
输入: 4

常见面试题，去年的面试问的简直都是口述思路，较少实现。支流思路是利用堆排序、疾速排序找出第 K 大的元素。应用优先队列也可实现指标。

堆排序法

void create(vector<int>& nums, int n) {for(int i = (n-1)/2; i >= 0; --i){adjust(nums, n, i);
        }
    }
    void adjust(vector<int>& nums, int n, int root) {
        int i = root;
        int child = i*2+1;
        while(child <= n) {if(child+1 <= n && nums[child] > nums[child+1]) ++child;
            if(nums[child] >= nums[i])break;
            swap(nums[i], nums[child]);
            i = child;
            child = child*2+1;
        }
    }
    int findKthLargest(vector<int>& nums, int k) {int len = nums.size();
        create(nums, k-1);
        for(int i = k; i< len; ++i) {if(nums[i] <= nums[0]) continue;
            swap(nums[i], nums[0]);
            adjust(nums, k-1, 0);
        }
        return nums[0];
    }

首先须要记住：在建堆的时候调整办法通常是 向下调整 。用堆排序解决这个问题能够优化的中央就是只建大小为 K 的小顶堆，之后遍历残余的数，若比堆顶元素大，则替换两个数，再调整堆。
工夫复杂度：建堆工夫复杂度为 O(k)，而后续最多经验 n - k 次调整，每次调整的工夫复杂度为 logk，因而工夫复杂度为 O(nlogk)
空间复杂度显然为 O(1)

为什么建堆的工夫复杂度为 O(n)？
由建堆算法可知，数组中每个非叶子节点都要进行一次向下调整算法，在向下调整算法中替换的次数相当于从该节点到叶子节点的高度，那么每一层中所有节点替换的次数为该层节点的个数乘以该节点到叶子节点的高度，比方，第一层的替换次数就是 20 h，那么对其进行累计求和，即可失去总的替换次数 S(n) = 20 h + 21 (h-1) + 22 (h – 2) + …… + 2h-2 2 +2h-1 1+ 2h * 0 = 2h+1 – (h + 2) = n – log2(n + 1)。因而，工夫复杂度为 O(n)

疾速排序法

int partition(vector<int>&nums, int l, int r) {int i = rand() % (r - l + 1) + l;
        swap(nums[i], nums[l]);
        int pivotkey = nums[l];
        while(l < r) {while(l < r && pivotkey >= nums[r]) r--;
            swap(nums[l], nums[r]);
            while(l < r && pivotkey <= nums[l]) l++;
            swap(nums[l], nums[r]);
        }
        return l;
    }
    int findKthLargest(vector<int>& nums, int k) {int left = 0, right = nums.size()-1;
        int index = partition(nums, left, right);
        while(index != k-1) {if(index < k-1) {left = index + 1;}
            else {right = index - 1;}
            index = partition(nums, left, right);
        }
        return nums[index];
    }

因为快排每次确定一个数的最终地位，而此题最终目标是找到第 K 个最大值，因而咱们做降序排序，每次确定一个 index 上的数，如果这个 index<k，则阐明咱们要找的数在左边，所以只须要做左边的 partition；同理，如果 index>k，则阐明要找的数在右边，做右边的 partition。
工夫复杂度：O(nlogn)
空间复杂度：O(1)

家喻户晓，当原序列有序时，快排效率会进化到 O(n²)，因而在 partition 前退出随机值随机选取中枢值，能够无效防止算法进化。

优先队列法

int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int> > q;
        for(int i = 0; i < k; ++i) {q.push(nums[i]);
        }
        int len = nums.size();
        for(int i = k; i < len; ++i) {if(nums[i] > q.top()) {q.pop();
                q.push(nums[i]);
            }
        }
        return q.top();}

事实上思路与堆排序是统一的，只不过用到了 STL。（但用官网函数就是快啊……）

退出移动版