题目:
给定整数数组 nums
和整数 k
,请返回数组中第 k
个最大的元素。
请留神,你须要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
本算法题目有两种比拟好的办法,别离为应用 小顶堆
和应用 疾速抉择
。
题解一:
首先咱们应用 小顶堆
的办法求解,先贴代码(Go 语言):
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool {return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) {h[i], h[j] = h[j], h[i] }
func (h IntHeap) Top() int {return h[0]
}
func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func findKthLargest(nums []int, k int) int {h := &IntHeap{}
heap.Init(h)
for _, num := range nums {if h.Len() < k {heap.Push(h, num)
} else if (*h)[0] < num {heap.Pop(h)
heap.Push(h, num)
}
}
return heap.Pop(h).(int)
}
首先咱们确定循环不变量:h
中始终存储了最多 k
个数组元素,且是目前遍历过的最大的 k
个元素,且其中最小的元素为(*h)[0]
。
h
是一个小顶堆,则 h
可能保障,退出其中的元素的最小的元素为(*h)[0]
。(小顶堆的概念可自行 Google)
初始化: h
中没有元素,不变式成立。
放弃: 在迭代过程中,依据 h
的元素数量,分为如下两种状况:
- 如果
h
中元素的个数小于k
,间接将本次迭代的数组元素num
退出到h
中。 - 如果
h
中元素的个数大于等于k
,则须要比拟以后h
中,最小的元素是否大于num
,若是,疏忽num
的解决,否则,将其替换为num
。
以上两种状况的后果均能够保障不变式成立。
终止: nums
中的所有元素均被遍历后算法终止,不变式成立。
最终 h
中的最小元素 (*h)[0]
即为数组 nums
的第 K
个最大元素。
复杂度剖析:
工夫复杂度:O(nlogn)
,建堆的工夫代价是 O(n)
,删除的总代价是O(klogn)
,因为 k < nk < n
,故渐进工夫简单为O(n + klogn) = O(nlogn)
。
空间复杂度:O(logn)
,即递归应用栈空间的空间代价。
题解二:
咱们同样能够应用 疾速抉择
的办法求解,先贴代码(Go 语言):
func findKthLargest(nums []int, k int) int {rand.Seed(time.Now().UnixNano())
return quickSelect(nums, 0, len(nums)-1, k)
}
func quickSelect(nums []int, l int, r int, k int) int {m := randomPartition(nums, l, r)
if r-m+1 == k {return nums[m]
} else if r-m+1 > k {return quickSelect(nums, m+1, r, k)
} else {return quickSelect(nums, l, m-1, k-(r-m+1))
}
}
func randomPartition(nums []int, l, r int) int {i := rand.Int()%(r-l+1) + l
nums[i], nums[r] = nums[r], nums[i]
return partition(nums, l, r)
}
func partition(nums []int, l int, r int) int {key := nums[r]
//all in [l,i) < key
//all in [i,j] > key
i := l
j := l
for j < r {if nums[j] < key {nums[i], nums[j] = nums[j], nums[i]
i++
}
j++
}
nums[i], nums[r] = nums[r], nums[i]
return i
}
疾速抉择
与疾速排序
很相似,应用了雷同的分治思维,(疾速排序
算法可参考这篇文章)将 疾速排序
的解决阶段 稍加批改即可。同时咱们这里的 疾速抉择
算法应用了 随机采样
的办法,进步了算法的性能。
复杂度剖析:
工夫复杂度:O(n)
,如上文所述,证实过程能够参考「《算法导论》9.2:冀望为线性的抉择算法」。
空间复杂度:O(log n)
,递归应用栈空间的空间代价的冀望为 O(logn)
。
两种解法的比照:
疾速抉择
算法工夫复杂度更低,且不须要额定的存储空间。然而必须事后晓得数组的总长度,所以适宜对定长数组的计算。堆
须要额定的k
个存储空间,且算法工夫复杂度绝对高一些。然而不须要事后晓得待处理数组的规模,所以适宜对流数据进行解决。