【leetcodeノート】215.配列内のK番目の最大要素

タイトルの説明
タイトルリンク: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& nums, int n) {
        for(int i = (n-1)/2; i >= 0; --i){
            adjust(nums, n, i);
        }
    }
    void adjust(vector& 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& 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サイズの小さなスタックのみを構築し,その後残りの数を遍歴し,スタック要素より大きい場合は2つの数を交換し,スタックを調整することである.時間複雑度:スタック構築時間複雑度はO(k)であり、その後はn-k回の調整が最も多く、毎回の調整時間複雑度はlogkであるため、時間複雑度はO(nlogk)空間複雑度は明らかにO(1)である.
なぜスタックを建てる時間の複雑さはO(n)なのか.スタックアルゴリズムから分かるように、配列内の非リーフノードごとに1回のダウンコンバートアルゴリズムが行われ、ダウンコンバートアルゴリズムで交換される回数はノードからリーフノードまでの高さに相当するが、各層におけるすべてのノード交換の回数は、その層ノードの個数にノードからリーフノードまでの高さを乗じたものであり、例えば、第1層の交換回数は20 hであり、合計交換回数S(n)=20 h+21(h−1)+22(h−2)+・・+2 h−2+2 h−1 1+2 h*0=2 h+1−(h+2)=n−log 2(n+1)が得られる.したがって,時間的複雑度はO(n)である.
クイックソート

int partition(vector&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& 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];
    }

速い列は毎回1つの数の最終位置を決定するため、この問題の最終目標はK番目の最大値を見つけることであるため、私たちは降順に並べ替えて、毎回1つのindex上の数を決定して、もしこのindexkならば、探す数が左にあることを説明して、左のpartitionをします.時間複雑度:O(nlogn)空間複雑度:O(1)
よく知られているように,元の配列が秩序化すると,高速排出効率はO(n)に劣化する.²),従ってpartition前にランダム値を加えて中枢値をランダムに選択することで,アルゴリズムの劣化を効果的に回避できる.
ゆうせんキューほう

int findKthLargest(vector& nums, int k) {
        priority_queue, greater > 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を用いたにすぎない.(でも公式関数では早いですよね…)