👣 K-ый наибольший элемент

Сложность: Лёгкая 

Условие задачи: Нужно создать класс по нахождению k-ого наибольшего элемента среди передаваемых значений. k-м считается элемент для отсортированного списка, а не по уникальности значения.

Класс содержит следующие методы:

- KthLargest(int k, int[] nums) иниициализирует класс;

- int add(int val) добавляет элемент в спискок и возвращает k-ый наименьший согласно условию.

Пример:

Ввод: ["KthLargest", "add", "add", "add", "add", "add"]

[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

Вывод: [null, 4, 5, 5, 8, 8]

Объяснение:

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

type elementsQueue []int

func (pq elementsQueue) isEmpty() bool {
 return pq.Len() == 0
}

func (pq elementsQueue) Len() int {
 return len(pq)
}

// Min-heap
func (pq elementsQueue) Less(i, j int) bool {
 return pq[i] < pq[j]
}

func (pq elementsQueue) Swap(i, j int) {
 pq[i], pq[j] = pq[j], pq[i]
}

func (pq *elementsQueue) Push(num interface{}) {
 *pq = append(*pq, num.(int))
}

func (pq *elementsQueue) Pop() interface{} {
 len := len(*pq)
 num := (*pq)[len-1]
 *pq = (*pq)[:len-1]
 return num
}

func (pq elementsQueue) Peek() interface{} {
 return pq[0]
}

type KthLargest struct {
 pq *elementsQueue
 k  int
}

func Constructor(k int, nums []int) KthLargest {
 pq := new(elementsQueue)
 for _, v := range nums {
  heap.Push(pq, v)
 }
 for pq.Len() > k {
  heap.Pop(pq)
 }
 return KthLargest{
  pq: pq,
  k:  k,
 }
}

func (this *KthLargest) Add(val int) int {
 if this.pq.Len() >= this.k {
  if val <= this.pq.Peek().(int) {
   return this.pq.Peek().(int)
  }

  heap.Pop(this.pq)
 }

 heap.Push(this.pq, val)
 return this.pq.Peek().(int)
}

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

Временная сложность: O(nlogn)O(nlogn)O(nlogn)

Пространственная сложность: O(k)O(k)O(k)