Python
快排法
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return self.quickSort(nums, k)
def quickSort(self, nums, count):
bigger = list()
same = list()
smaller = list()
label = random.choice(nums) # 随机选择用法
for item in nums:
if item > label:
bigger.append(item)
elif item < label:
smaller.append(item)
else:
same.append(item)
if count <= len(bigger): # 注意: 这里一定包含等号
return self.quickSort(bigger, count)
elif count > len(bigger) + len(same): # 注意: 这里一定不包含等号
return self.quickSort(smaller, count - len(bigger) - len(same))
else:
return label
小根堆
最大的K个元素 => 小根堆(类似上窄下宽的梯形),最大的第k个就是堆顶元素
最小的K个元素 => 大根堆(类似倒三角形),最小的第k个就是堆顶元素
python中小根堆用法:https://blog.csdn.net/weixin_40134371/article/details/139996858
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
min_heap = []
for i in range(k):
heapq.heappush(min_heap, nums[i])
for i in range(k, len(nums)):
heapq.heappushpop(min_heap, nums[i])
return min_heap[0]
偷鸡摸狗法
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# nums.sort(reverse=True) # 这种排序也可
return sorted(nums)[len(nums) - k]
Java
法1:小根堆
最大的K个元素 => 小根堆(类似上窄下宽的梯形)
最小的K个元素 => 大根堆(类似倒三角形)
必须掌握!!!
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>();
for (int i = 0; i < k; ++i) {
q.offer(nums[i]);
}
for (int i = k; i < nums.length; ++i) {
if (nums[i] > q.peek()) {
q.poll();
q.offer(nums[i]);
}
}
return q.peek();
}
}
法2:基于快排
class Solution {
public int findKthLargest(int[] nums, int k) {
List<Integer> list = new ArrayList<>();
for (int i : nums) {
list.add(i);
}
return quickSelect(list, k);
}
public int quickSelect(List<Integer> list, int k) {
int n = list.size();
Random rand = new Random();
int rInx = rand.nextInt(n); // 生成0 ~ n-1之间的整数
List<Integer> big = new ArrayList<>();
List<Integer> same = new ArrayList<>();
List<Integer> small = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (list.get(i) > list.get(rInx)) {
big.add(list.get(i));
} else if (list.get(i) == list.get(rInx)) {
same.add(list.get(i));
} else {
small.add(list.get(i));
}
}
if (big.size() >= k) {
return quickSelect(big, k);
} else if (k > (big.size() + same.size())) {
return quickSelect(small, k - (big.size() + same.size()));
} else {
return list.get(rInx);
}
}
}