经典手机网站,网站可以多个域名吗,wordpress themepath,wordpress标签样式表目录 题目#xff1a;在数组中找第K大的元素解法1#xff1a;维护长度为k的最小堆#xff0c;遍历n-k个元素#xff0c;逐一和堆顶值对比后#xff0c;和堆顶交换#xff0c;最后返回堆顶复杂度#xff1a;时间复杂度 O ( k ( n − k ) l o g k ) O(k(n-k)logk) O(k(n−… 目录 题目在数组中找第K大的元素解法1维护长度为k的最小堆遍历n-k个元素逐一和堆顶值对比后和堆顶交换最后返回堆顶复杂度时间复杂度 O ( k ( n − k ) l o g k ) O(k(n-k)logk) O(k(n−k)logk)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 解法2构建长度为n的最大堆遍历k次每次删除堆顶且堆长度-1最后返回堆顶k较小时此法更优复杂度时间复杂度 O ( n k l o g n ) O(nklogn) O(nklogn)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 题目堆排序思路分析构建长度为n的最大堆依次删除堆顶并逆序放到数组尾部且堆长度-1n-1次后数组则为升序复杂度时间复杂度 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))、空间复杂度 O ( 1 ) O(1) O(1)Go代码 题目合并K个排序链表思路分析维护长度为k的最小堆依次删除堆顶接到返回链表上纵向拼接注意取值时判断空链表复杂度时间复杂度 O ( k n l o g k ) O(knlogk) O(knlogk)、空间复杂度 O ( 1 ) O(1) O(1)Go代码 题目在数组中找第K大的元素
题目链接LeetCode-215. 数组中的第K个最大元素
解法1维护长度为k的最小堆遍历n-k个元素逐一和堆顶值对比后和堆顶交换最后返回堆顶
复杂度时间复杂度 O ( k ( n − k ) l o g k ) O(k(n-k)logk) O(k(n−k)logk)、空间复杂度 O ( 1 ) O(1) O(1)
Go代码
func findKthLargest(nums []int, k int) int {length : len(nums)if k length {return -1}makeMinHeap(nums, k)for i:k;ilength;i {if nums[i] nums[0] {nums[0], nums[i] nums[i], nums[0]minHeap(nums, 0, k)}}return nums[0]
}func makeMinHeap(arr []int, length int) {// 从最后一个非叶子节点开始for i:(length/2-1); i0; i-- {minHeap(arr, i, length)}
}// 最小堆化
func minHeap(arr []int, i int, length int) {left, right : 2*i1, 2*i2min : iif left length arr[left] arr[min] {min left}if right length arr[right] arr[min] {min right}if min ! i {arr[i], arr[min] arr[min], arr[i]minHeap(arr, min, length)}
}解法2构建长度为n的最大堆遍历k次每次删除堆顶且堆长度-1最后返回堆顶k较小时此法更优
复杂度时间复杂度 O ( n k l o g n ) O(nklogn) O(nklogn)、空间复杂度 O ( 1 ) O(1) O(1)
Go代码
func findKthLargest(nums []int, k int) int {length : len(nums)if k length {return -1}// 将nums构建为一个最大堆makeMaxHeap(nums, length)for i:1; ik; i {nums[0], nums[length-i] nums[length-i], nums[0]maxHeap(nums, 0, length-i)}return nums[0]
}// 最大堆
func makeMaxHeap(arr []int, length int) {// 第一个非叶子节点for i:(length/2-1); i0; i-- {maxHeap(arr, i, length)}
}
// 最大堆化
func maxHeap(arr []int, i int, length int) {l, r, max : 2*i1, 2*i2, iif llength arr[l] arr[max] {max l}if rlength arr[r] arr[max] {max r}if max ! i {arr[max], arr[i] arr[i], arr[max]maxHeap(arr, max, length)}
}题目堆排序
题目链接LeetCode-912. 排序数组
思路分析构建长度为n的最大堆依次删除堆顶并逆序放到数组尾部且堆长度-1n-1次后数组则为升序
复杂度时间复杂度 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))、空间复杂度 O ( 1 ) O(1) O(1)
Go代码
func sortArray(nums []int) []int {length : len(nums)if length 1 {return nums}makeMaxHeap(nums, length)for i:length-1; i0; i-- {nums[0], nums[i] nums[i], nums[0]maxHeap(nums, 0, i)}return nums
}
// 构建最大堆
func makeMaxHeap(nums []int, length int) {// 第一个非叶子结点for i:length/2-1; i0; i-- {maxHeap(nums, i, length)}
}
// 最大堆化
func maxHeap(nums []int, i int, length int) {l, r, max : 2*i1, 2*i2, iif llength nums[l] nums[max] {max l}if rlength nums[r] nums[max] {max r}if max ! i {nums[max], nums[i] nums[i], nums[max]maxHeap(nums, max, length)}
}题目合并K个排序链表
题目链接LeetCode-23. 合并 K 个升序链表
思路分析维护长度为k的最小堆依次删除堆顶接到返回链表上纵向拼接注意取值时判断空链表
复杂度时间复杂度 O ( k n l o g k ) O(knlogk) O(knlogk)、空间复杂度 O ( 1 ) O(1) O(1)
Go代码
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/
func mergeKLists(lists []*ListNode) *ListNode {length : len(lists)if length 1 {return lists[0]}// 去除空数组for i:0; ilength; i {if lists[i] nil {lists[i], lists[length-1] lists[length-1], lists[i]length--i--}}newList : ListNode{}tmp : newList// 最小化makeMinHeap(lists, length)for length 0 lists[0] ! nil {// 取出当前最小tmp.Next ListNode{Val:lists[0].Val}tmp tmp.Nextlists[0] lists[0].Nextif lists[0] nil {lists[0], lists[length-1] lists[length-1], lists[0]length--}if length 0 lists[0] ! nil {minHeap(lists, 0, length)}}return newList.Next
}func makeMinHeap(arr []*ListNode, length int) {for i:length/2-1; i0; i-- {minHeap(arr, i, length)}
}func minHeap(arr []*ListNode, i, length int) {left, right, min : 2*i1, 2*i2, iif leftlength arr[left].Val arr[min].Val {min left}if rightlength arr[right].Val arr[min].Val {min right}if min ! i {arr[min], arr[i] arr[i], arr[min]minHeap(arr, min, length)}
}
