README.md

title	subtitle	date	lastmod	draft	author	authorLink	description	license	images	tags	categories	featuredImage	featuredImagePreview	hiddenFromHomePage	hiddenFromSearch	twemoji	lightgallery	ruby	fraction	fontawesome	linkToMarkdown	rssFullText	toc	code	math	mapbox	share	comment	library	seo
0703. Kth Largest Element in a Stream	https://leetcode.com/problems/kth-largest-element-in-a-stream/	2023-01-22 21:20:00 +0800	2023-01-22 21:20:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	0703.Kth-Largest-Element-in-a-Stream			LeetCode Go Easy Kth Largest Element in a Stream Heap Priority Queue	LeetCode			false	false	false	true	true	true	true	false	false	enable auto true true	copy maxShownLines true 200	enable		enable true	enable true	css js	images

0703. Kth Largest Element in a Stream

題目

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums. int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

Example 1:

Input ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output [null, 4, 5, 5, 8, 8]

Explanation KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8

Constraints:

1 <= k <= 104 0 <= nums.length <= 104 -104 <= nums[i] <= 104 -104 <= val <= 104 At most 104 calls will be made to add. It is guaranteed that there will be at least k elements in the array when you search for the kth element. Accepted 479.1K Submissions 846.4K Acceptance Rate 56.6%

題目大意

設計一個找到數據流中第 k 大元素的類（class）。 注意是排序後的第 k 大元素，不是第 k 個不同的元素。 請實現 KthLargest 類：

• KthLargest（int k， int[] nums） 使用整數 k 和整數流 nums 初始化物件。
• int add（int val） 將 val 插入數據流 nums 後，返回當前數據流中第 k 大的元素。

解題思路

這題考察優先順序佇列的使用，可以先做下這道類似的題目 215.陣列中的第 K 個最大元素。

golang container/heap

Big O

時間複雜 : 初始化時間複雜度為： O(nlog⁡k) ，其中 n 為初始化時 nums 的長度; 單次插入時間複雜度為： O(log⁡k)

空間複雜 : O(k)。 需要使用優先佇列存儲前 k 大的元素

來源

• https://leetcode.com/problems/kth-largest-element-in-a-stream/
• https://leetcode.cn/problems/kth-largest-element-in-a-stream/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0703.Kth-Largest-Element-in-a-Stream/main.go

package kthlargestelementinastream

import (
	"container/heap"
	"sort"
)

/**
 * Your KthLargest object will be instantiated and called as such:
 * obj := Constructor(k, nums);
 * param_1 := obj.Add(val);
 */

// 時間複雜 O(), 空間複雜 O()
type KthLargest struct {
	sort.IntSlice
	k int
}

func Constructor(k int, nums []int) KthLargest {
	kl := KthLargest{k: k}
	for _, val := range nums {
		kl.Add(val)
	}
	return kl
}

func (kl *KthLargest) Add(val int) int {
	heap.Push(kl, val)
	if kl.Len() > kl.k {
		heap.Pop(kl)
	}
	return kl.IntSlice[0]
}

func (kl *KthLargest) Push(v interface{}) {
	kl.IntSlice = append(kl.IntSlice, v.(int))
}

func (kl *KthLargest) Pop() interface{} {
	a := kl.IntSlice
	v := a[len(a)-1]
	kl.IntSlice = a[:len(a)-1]
	return v
}

func KthLargestStream(k int, nums []int, elem []int) []int {
	obj := Constructor(k, nums)
	result := []int{0}
	for _, val := range elem {
		obj.Add(val)
		result = append(result, obj.IntSlice[0])
	}

	return result
}

Benchmark