成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[Leetcode] Kth Largest Element in an Array 數(shù)組中第K大元

Rocko / 419人閱讀

摘要：優(yōu)先隊(duì)列復(fù)雜度時(shí)間空間思路遍歷數(shù)組時(shí)將數(shù)字加入優(yōu)先隊(duì)列堆，一旦堆的大小大于就將堆頂元素去除，確保堆的大小為。如果這個(gè)分界點(diǎn)是，說明分界點(diǎn)的數(shù)就是第個(gè)數(shù)。

Kth Largest Element in an Array 
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.


For example, Given [3,2,1,5,6,4] and k = 2, return 5.


Note:  You may assume k is always valid, 1 ≤ k ≤ array"s length.
優(yōu)先隊(duì)列 復(fù)雜度

時(shí)間 O(NlogK) 空間 O(K)

思路

遍歷數(shù)組時(shí)將數(shù)字加入優(yōu)先隊(duì)列（堆），一旦堆的大小大于k就將堆頂元素去除，確保堆的大小為k。遍歷完后堆頂就是返回值。

代碼 
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue p = new PriorityQueue();
        for(int i = 0 ; i < nums.length; i++){
            p.add(nums[i]);
            if(p.size()>k) p.poll();
        }
        return p.poll();
    }
}
排序法 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(1)

思路

將數(shù)組排序后，返回第k個(gè)元素。

代碼 
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}
快速選擇 Quick Select 復(fù)雜度

時(shí)間 Avg O(N) Worst O(N^2) 空間 O(1)

思路

跟快速排序一個(gè)思路。先取一個(gè)樞紐值，將數(shù)組中小于樞紐值的放在左邊，大于樞紐值的放在右邊，具體方法是用左右兩個(gè)指針，如果他們小于樞紐值則將他們換到對(duì)面，一輪過后記得將樞紐值賦回分界點(diǎn)。如果這個(gè)分界點(diǎn)是k，說明分界點(diǎn)的數(shù)就是第k個(gè)數(shù)。否則，如果分界點(diǎn)大于k，則在左半邊做同樣的搜索。如果分界點(diǎn)小于k，則在右半邊做同樣的搜索。

注意

helper函數(shù)的k是k-1，因?yàn)槲覀兿聵?biāo)從0開始的，我們要比較k和下標(biāo)，來確定是否左半部分有k個(gè)數(shù)字。

互換左右時(shí)，也要先判斷left <= right

代碼 
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k - 1, 0, nums.length - 1);
    }
    
    private int quickSelect(int[] arr, int k, int left, int right){
        int pivot = arr[(left + right) / 2];
        int orgL = left, orgR = right;
        while(left <= right){
            // 從右向左找到第一個(gè)小于樞紐值的數(shù)
            while(arr[left] > pivot){
                left ++;
            }
            // 從左向右找到第一個(gè)大于樞紐值的數(shù)
            while(arr[right] < pivot){
                right --;
            }
            // 將兩個(gè)數(shù)互換
            if(left <= right){
                swap(arr, left, right);
                left ++;
                right --;
            }
        }
        // 最后退出的情況應(yīng)該是右指針在左指針左邊一格
        // 這時(shí)如果右指針還大于等于k，說明kth在左半邊
        if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right);
        // 這時(shí)如果左指針還小于等于k，說明kth在右半邊
        if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR);
        return arr[k];
    
    }
    
    private void swap(int[] arr, int idx1, int idx2){
        int tmp = arr[idx1] + arr[idx2];
        arr[idx1] = tmp - arr[idx1];
        arr[idx2] = tmp - arr[idx2];
    
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64481.html

相關(guān)文章

  • Kth Largest Element in an Array，Top K Frequent Ele

    摘要：解題思路，默認(rèn)就是隊(duì)列頂端是最小元素，第大元素，我們只要限制的大小為即可，最后隊(duì)列頂端的就是第大元素。代碼解題思路利用存入，之后采用，并限制最多放個(gè)元素。 Kth Largest Element in an ArrayFind the kth largest element in an unsorted array. Note that it is the kth largest el...

    Tony_Zby 評(píng)論0 收藏0

  • [LintCode] Kth Largest Element [PriorityQueue]

    摘要：可以不要用太簡單的方法。先把它裝滿，再和隊(duì)列頂端的數(shù)字比較，大的就替換掉，小的就。遍歷完所有元素之后，頂部的數(shù)就是第大的數(shù)。 Problem Find K-th largest element in an array. Example In array [9,3,2,4,8], the 3rd largest element is 4.In array [1,2,3,4,5], the...

    Hwg 評(píng)論0 收藏0

  • leetcode378. Kth Smallest Element in a Sorted Matr

    摘要：因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構(gòu)成第個(gè)元素的值進(jìn)行堆排序就可以了。 題目要求 Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that...

    dailybird 評(píng)論0 收藏0

  • [Leetcode] Kth Smallest Element in a BST 二叉搜索樹第k小節(jié)

    摘要：中序遍歷復(fù)雜度時(shí)間空間思路因?yàn)樽蠊?jié)點(diǎn)小于根節(jié)點(diǎn)小于右節(jié)點(diǎn)，二叉搜索樹的一個(gè)特性就是中序遍歷的結(jié)果就是樹內(nèi)節(jié)點(diǎn)從小到大順序輸出的結(jié)果。這里采用迭代形式，我們就可以在找到第小節(jié)點(diǎn)時(shí)馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個(gè)問題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...

    Dean 評(píng)論0 收藏0

  • [LeetCode] 378. Kth Smallest Element in a Sorted M

    摘要：先放一行，或一列把堆頂?shù)淖钚≡厝〕鰜?，取次，如果該有下一行下一列的，放入堆中最小的個(gè)元素已經(jīng)在上面的循環(huán)被完了，下一個(gè)堆頂元素就是 Problem Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in...

    Shihira 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<