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

Метод 1: сортировка массива
Один простой подход — отсортировать массив в порядке убывания и вернуть K-й элемент. Вот фрагмент кода Scala для этого метода:

def findKthLargest(nums: Array[Int], k: Int): Int = {
  val sortedArray = nums.sortWith(_ > _)
  sortedArray(k - 1)
}

Метод 2: использование приоритетной очереди
Другой эффективный подход предполагает использование приоритетной очереди или максимальной кучи. Мы можем создать максимальную кучу размером K и перебирать массив, добавляя элементы в кучу. Если размер кучи превышает K, мы удаляем максимальный элемент. Наконец, корнем кучи будет K-й по величине элемент. Ниже представлена ​​реализация Scala:

import scala.collection.mutable.PriorityQueue
def findKthLargest(nums: Array[Int], k: Int): Int = {
  val maxHeap = PriorityQueue.empty[Int].reverse
  nums.foreach(num => {
    maxHeap.enqueue(num)
    if (maxHeap.size > k)
      maxHeap.dequeue()
  })
  maxHeap.dequeue()
}

Метод 3: Алгоритм быстрого выбора
Алгоритм быстрого выбора — это эффективный способ найти K-й элемент в несортированном массиве. Он похож на алгоритм быстрой сортировки, но фокусируется на разделении только необходимых частей массива. Вот реализация Scala:

import scala.util.Random
def findKthLargest(nums: Array[Int], k: Int): Int = {
  def swap(arr: Array[Int], i: Int, j: Int): Unit = {
    val temp = arr(i)
    arr(i) = arr(j)
    arr(j) = temp
  }
  def partition(arr: Array[Int], left: Int, right: Int): Int = {
    val pivotIndex = Random.between(left, right + 1)
    val pivotValue = arr(pivotIndex)
    swap(arr, pivotIndex, right)
    var i = left
    for (j <- left until right) {
      if (arr(j) <= pivotValue) {
        swap(arr, i, j)
        i += 1
      }
    }
    swap(arr, i, right)
    i
  }
  def quickselect(arr: Array[Int], left: Int, right: Int, k: Int): Int = {
    if (left == right) return arr(left)
    val pivotIndex = partition(arr, left, right)
    if (k == pivotIndex) arr(k)
    else if (k < pivotIndex) quickselect(arr, left, pivotIndex - 1, k)
    else quickselect(arr, pivotIndex + 1, right, k)
  }
  quickselect(nums, 0, nums.length - 1, nums.length - k)
}

В этой статье мы рассмотрели три различных метода поиска K-го по величине элемента массива с помощью Scala. Мы обсудили сортировку массива с использованием очереди приоритетов и алгоритма быстрого выбора. Каждый метод имеет свои преимущества и недостатки с точки зрения временных затрат и сложности реализации. Понимая эти методы, вы сможете выбрать наиболее подходящий подход для ваших конкретных требований.