成人电影一区二区,色逼中文字幕,波多野结衣无码AV,小黄片下载免费视频,丁香花五月激,久久久91精品国产一区陈可心 ,国产精品AⅤ电影,日本十八禁视频

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 數(shù)組中的第K個最大元素，我們先來看題面：

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

題意

在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 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

說明:

你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長度。

解題

利用快速排序，快速定位第k大的元素，具體可看代碼注釋

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums, 0, nums.length-1, k);
    }
    
    int find(int[] nums, int s, int e, int k) {
        // 設(shè)定flag，默認用nums[s]
        int flag = nums[s];
        int ss = s;
        int ee = e;
        while(ss<ee) {
            // 從后向前找到第一個比flag大的數(shù)
            while(ss<ee && nums[ee] <= flag)
                ee--;
            // 交換flag和比flag大的數(shù)
            nums[ss] = nums[ee];
            nums[ee] = flag;
            // 從前向后找到第一個小于等于flag的數(shù)
            while(ss<ee && nums[ss] > flag)
                ss++;
            // 交換flag和比flag小的數(shù)
            nums[ee] = nums[ss];
            nums[ss] = flag;
        }
        // 返回結(jié)果
        if(ss + 1 == k)
            return nums[ss];
        // 找到的數(shù)比k小，更新s
        else if(ss + 1 < k)
            return find(nums, ss+1, e, k);
        // 找到的數(shù)比k大，更新e
        else 
            return find(nums, s, ss-1, k);
    }
}