目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
寻找第K大
访问量:1410
一、简介
有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
要求:时间复杂度 O(nlogn)O(nlogn),空间复杂度 O(1)O(1)
示例1
输入:[1,3,5,2,2],5,3
返回值 2
示例1
输入:[10,10,9,9,8,7,5,6,4,3,4,2],12,3
返回值 9
二、解法
/** * 思路: 使用最大的 k个数字,构建一个最小堆,那么堆顶元素,即第k大的数字 * @param a int整型一维数组 * @param n int整型 * @param K int整型 * @return int整型 */ func findKth( a []int , n int , K int ) int { // write code here // 先使用前K个元素,构建一个最小堆 heap := a[:K] // 将 heap 调整为 最小堆 for index := K/2 - 1; index >=0; index -- { jumpMinHeap(heap, index) } // 将剩下的元素依次插入堆中 if n > K { for index := K; index < n; index ++ { // 如果当前节点,小于等于堆顶元素,直接丢弃 if a[index] <= heap[0] { continue } // 替换堆定元素,再次调整 heap[0] = a[index] jumpMinHeap(heap, 0) } } // 返回堆顶元素 return heap[0] } /** * @param data 需要调整的堆 * @param index 需要调整的节点 */ func jumpMinHeap(data []int, index int) { leftIndex := index *2 + 1 rightIndex := index*2 + 2 // 无左右节点 if leftIndex >= len(data) { return } // 无右节点 if rightIndex >= len(data) { if data[leftIndex] >= data[index] { return } // 交换 左节点 和 根节点 data[leftIndex], data[index] = data[index], data[leftIndex] // 因当前节点,无右节点,左和根节点交换后,不需要再递归比较 return } // 根节点已是最小值,不需要再次比较 if data[index] <= data[leftIndex] && data[index] <= data[rightIndex] { return } // 左节点是最小值 if data[leftIndex] < data[index] && data[leftIndex] <= data[rightIndex] { // 交换 左节点 和 根节点 data[leftIndex], data[index] = data[index], data[leftIndex] // 继续递归 左节点 jumpMinHeap(data, leftIndex) return } // 如果右节点是最小值 if data[rightIndex] < data[index] && data[rightIndex] < data[leftIndex] { // 交换 左节点 和 根节点 data[rightIndex], data[index] = data[index], data[rightIndex] // 继续递归 左节点 jumpMinHeap(data, rightIndex) return } }
题目来源:牛客
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助