Question 215: Kth Largest Element in an Array?Difficulty: Medium

題目描述

在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

示例：

輸入: [3,2,1,5,6,4] 和 k = 2輸出: 5輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4輸出: 4

說明:

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

題目分析

顯然這道題可以先排序，再去找第K大的值，但這種暴力解法顯然不是最優(yōu)解。在這里我們可以維護一個大小為K的最小堆minheap來實現(xiàn)。

本題目的算法并不難，但我們需要了解一下堆的概念。

關(guān)于堆

堆就是用數(shù)組實現(xiàn)的二叉樹，所有它沒有使用父指針或者子指針。堆根據(jù)“堆屬性”來排序，“堆屬性”決定了樹中節(jié)點的位置。

堆的常用方法：

?構(gòu)建優(yōu)先隊列?支持堆排序?快速找出一個集合中的最小值(或者最大值)

堆分為兩種：最大堆?和?最小堆，兩者的差別在于節(jié)點的排序方式。

在最大堆中，父節(jié)點的值比每一個子節(jié)點的值都要大。在最小堆中，父節(jié)點的值比每一個子節(jié)點的值都要小。這就是所謂的“堆屬性”，并且這個屬性對堆中的每一個節(jié)點都成立。

這是一個最大堆，，因為每一個父節(jié)點的值都比其子節(jié)點要大。10?比?7?和?2?都大。7?比?5?和?1都大。

根據(jù)這一屬性，那么最大堆總是將其中的最大值存放在樹的根節(jié)點。而對于最小堆，根節(jié)點中的元素總是樹中的最小值。堆屬性非常的有用，因為堆常常被當做優(yōu)先隊列使用，因為可以快速的訪問到“最重要”的元素。

題解

顯然，遍歷數(shù)組中的元素，并維護一個大小為K的minHeap，最后堆頂元素即為所求。遍歷每個元素，并每次都要進行一次heapify，則時間復雜度為O(N log K)，由于維護了大小為K的minHeap則空間復雜度為O(log K)。

//Java 解法class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>(){ @Override public int compare(Integer o1, Integer o2){ if(o1.equals(o2)) return 0; return o1 < o2 ? -1 : 1; } } ); for(int i = 0; i < nums.length; i++){ if(minHeap.size() < k){ minHeap.add(nums[i]); }else if(nums[i] > minHeap.peek()){ minHeap.poll(); minHeap.add(nums[i]); } } return minHeap.poll(); }}#python 解法class Solution: def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ return heapq.nlargest(k, nums)[-1]

總結(jié)

以上是生活随笔為你收集整理的vector删除第i个元素_LeetCode每日一题 Q215数组中的第K个最大元素的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。