Учитывая массив целых чисел nums и целое число k, возвратите K-й наибольший элемент в массиве.

Обратите внимание, что это Kth самый большой элемент в отсортированном порядке, а не Kth отдельный элемент.

Вы должны решить его за O(n) времени сложности.

Постановка задачи взята с: https://leetcode.com/problems/Kth-largest-element-in-an-array.

Пример 1:

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Пример 2:

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4

Ограничения:

- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4

Решения для K-го самого большого элемента в массиве

Подход 1: пузырьковая сортировка

Мы можем использовать пузырьковую сортировку, чтобы найти K-й самый большой элемент в массиве.

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

Фрагмент C++ этого подхода выглядит следующим образом:

// A function to implement bubble sort
void bubbleSort(vector<int>& nums, int n){
    int i, j;

    // run the outer loop k - 1 times
    for (i = 0; i < k; i++)
        for (j = 0; j < n - i - 1; j++)
            if (nums[j] > nums[j + 1])
                swap(nums[j], nums[j + 1]);

    return nums[k - 1];
}

Временная сложность пузырьковой сортировки составляет O(n ^ 2). Но в этом случае мы запускаем внешний цикл k раз. Временная сложность этого подхода составляет O(n * k).

Мы не используем дополнительное пространство, поэтому сложность пространства составляет O(1).

Подход 2: сортировка

Наивный подход состоит в том, чтобы отсортировать данный массив в порядке убывания и вернуть элемент индекса k — 1 (0 — индексация на основе).

Фрагмент C++ приведенного выше подхода выглядит следующим образом:

// C++ code for K largest elements in an array
int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();

    sort(nums, nums + n, greater<int>());

    return nums[k - 1];
}

Временная сложность этого подхода составляет O(n * log(n)),, а пространственная сложность — O(1).

Подход 3: минимальная куча

Мы создаем минимальную кучу размера K и сравниваем корень минимальной кучи с другими элементами массива. Если элемент больше корня, мы меняем значения местами и увеличиваем кучу.

Нам нужно выполнить следующие шаги, чтобы найти K-й самый большой элемент в массиве:

  1. Создайте минимальную кучу для первых k элементов массива: от nums[0] до nums[k — 1].
  2. Перебрать оставшиеся элементы от nums[k] до nums[n — 1].
  3. Сравните элемент массива с корнем кучи.
  4. Если элемент больше, чем корень, добавьте кучу, иначе ничего не делайте.
  5. После выполнения вышеуказанных шагов наша куча Min имеет K самых больших элементов массива, а корень — это K-й самый большой элемент.

Фрагмент C++ этого подхода выглядит следующим образом:

int swap(int& x, int& y) {
    int temp = x;
    x = y;
    y = temp;
}

// Min Heap Class
class MinHeap {
    int size;
    int* arr;

public:
    MinHeap(int size, int input[]);
    void heapify(int i);
    void buildHeap();
};

MinHeap::MinHeap(int size, int input[]) {
    this->size = size;
    this->arr = input;

    buildHeap();
}

// Min Heapify function, that assumes
// 2 * i + 1 and 2 * i + 2 are min heap and
// fix min heap property for i
void MinHeap::heapify(int i) {
    // if Leaf Node, simply return
    if (i >= size / 2)
        return;

    int smallest;

    // index of left node
    int left = 2 * i + 1;

    // index of right node
    int right = 2 * i + 2;

    // Select minimum from left node and
    // current node i, and store the minimum
    // index in smallest variable
    smallest = arr[left] < arr[i] ? left : i;

    // If right child exist, compare and
    // update the smallest variable
    if (right < size)
        smallest = arr[right] < arr[smallest] ? right : smallest;

    // If Node i violates the min heap
    // property, swap  current node i with
    // smallest to fix the min-heap property
    // and recursively call heapify for node smallest.
    if (smallest != i) {
        swap(arr[i], arr[smallest]);
        heapify(smallest);
    }
}

// Build Min Heap
void MinHeap::buildHeap() {
    // Calling Heapify for all non leaf nodes
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(i);
    }
}

int findKthLargest(vector<int>& nums[], int size, int k) {
    // create Min Heap for given array with only k elements
    MinHeap* m = new MinHeap(k, nums);

    // Loop For each element in array
    // after the kth element
    for (int i = k; i < size; i++) {
        // if current element is smaller
        // than minimum element, do nothing
        // and continue to next element
        if (nums[0] > nums[i])
            continue;

        // Otherwise Change minimum element to
        // current element, and call heapify to
        // restore the heap property
        else {
            nums[0] = nums[i];
            m->heapify(0);
        }
    }

    // now min heap contains k maximum elements, print the root element as it is the
    // Kth largest element of the array
    return nums[0];
}

Временная сложность этого подхода составляет O(n * log k), а пространственная сложность — O(k).

Подход 4: приоритетная очередь

Вместо Min Heap мы можем использовать Приоритетную очередь, чтобы получить K-й самый большой элемент.

Примечание. Приоритетная очередь реализована как Max Heap по умолчанию в C++.

Нам нужно выполнить следующие шаги, чтобы найти K-й самый большой элемент в массиве:

  1. Перебрать массив и вставить элементы в очередь приоритетов.
  2. Если размер очереди превышает k, извлеките элемент из приоритетной очереди.
  3. После того, как мы выполнили итерацию по массиву, верните верхний элемент приоритетной очереди.

Фрагмент C++ этого подхода выглядит следующим образом:

int findKthLargest(vector<int>& nums, int k) {
    // initialize priority queue
    priority_queue<int, vector<int>, greater<int>> pq;

    // push all the elements
    for (int i = 0; i < nums.size(); i++) {
        pq.push(nums[i]);

        // if the queue side exceeds k, pop the top element
        if (pq.size() > k) {
            pq.pop();
        }
    }

    // return the top element of the priority queue
    return pq.top();
}

Временная сложность этого подхода составляет O(n * log k), а пространственная сложность — O(k).

Подход 5: использование бинарного дерева поиска

Мы можем создать Двоичное дерево поиска из элементов массива и получить K самых больших элементов массива.

Нам необходимо выполнить следующие шаги:

  1. Создайте BST, перебирая элементы массива.
  2. Пройдите BST в обратном порядке K раз.
  3. Вернуть K-й самый большой элемент.

Фрагмент C++ этого подхода выглядит следующим образом:

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

class Tree {
public:
    Node* root = NULL;
    void addNode(int data) {
        Node* newNode = new Node();
        newNode->data = data;

        if (!root) {
            root = newNode;
        } else {
            Node* cur = root;
            while (cur) {
                if (cur->data > data) {
                    if (cur->left) {
                        cur = cur->left;
                    } else {
                        cur->left = newNode;
                        return;
                    }
                } else {
                    if (cur->right) {
                        cur = cur->right;
                    } else {
                        cur->right = newNode;
                        return;
                    }
                }
            }
        }
    }

    void printGreatest(int& K, vector<int>& sol, Node* node) {
        if (!node || K == 0)
            return;

        printGreatest(K, sol, node->right);

        if (K <= 0)
            return;

        sol.push_back(node->data);
        K--;

        printGreatest(K, sol, node->left);
    }
};

int findKthLargest(vector<int>& nums, int k) {
    vector<int> sol;
    Tree tree = new Tree();

    for (int i = 0; i < nums.size(); i++) {
        tree.addNode(nums[i]);
    }

    tree.printGreatest(k, sol, tree.root);

    return sol[k - 1];
}

Временная сложность этого подхода составляет O(n * log(n)). Сложность пространства составляет O(n).

Подход 6: использование быстрой сортировки

Мы можем изменить алгоритм быстрой сортировки, чтобы найти K-й самый большой элемент. Давайте проверим алгоритм непосредственно.

Алгоритм

// findKthLargest(vector<int>& nums, int k)
- set n = nums.size()

- if n == 1
  - return nums[0]
- end if

- set l = 0, h = n - 1
  target = n - k

- loop while l <= h
  - set pivot = partition(nums, l, h)

  - if pivot < target
    - set l = pivot + 1
  - else if pivot > target
    - set h = pivot - 1
  - else
    - return nums[pivot]
  - end if
- end while

- return -1

// partition(vector<int> &nums, int l, int h)
- set high = nums[h]
      start = l

- loop for i = l; i < h; i++
  - if nums[i] < high
    - swap(nums[start], nums[i])
    - start++
  - end if
- end for

- swap(nums[start], nums[h])

- return start

Временная сложность описанного выше подхода составляет O(n * log(n)), а пространственная сложность — O(1).

Ознакомьтесь с нашими решениями на C++, Golang и Javascript.

С++ решение

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();

        // if nums size is 1 return the first element
        if (n == 1) {
            return nums[0];
        }

        int l = 0, h = n - 1;

        // set target to n - k
        int target = n - k;

        while (l <= h) {
            // set pivot with the value returned by partition function
            int pivot = partition(nums, l, h);

            // if the pivot is less than the target, search the right side
            if (pivot < target) {
                l = pivot + 1;
            } else if (pivot > target) {
                // if the pivot is greater than the target, search the left side
                h = pivot - 1;
            } else {
                // if the pivot is equal to the target, return nums[pivot]
                return nums[pivot];
            }
        }

        return -1;
    }

    int partition(vector<int> &nums, int l, int h) {
        int high = nums[h];
        int start = l;

        for (int i = l; i < h; i++) {
            // if nums[i] is less than high, then swap nums[start] with nums[i]
            if (nums[i] < high) {
                swap(nums[start], nums[i]);
                start++;
            }
        }

        //swap nums[start] with nums[h]
        swap(nums[start], nums[h]);

        return start;
    }
};

Голанг решение

func findKthLargest(nums []int, k int) int {
    n := len(nums)

    // if nums size is 1 return the first element
    if n == 1 {
        return nums[0]
    }

    l, h := 0, n - 1

    // set target to n - k
    target := n - k

    for l <= h {
        // set pivot with the value returned by partition function
        pivot := partition(nums, l, h)

        // if the pivot is less than the target, search the right side
        if pivot < target {
            l = pivot + 1
        } else if pivot > target {
            // if the pivot is greater than the target, search the left side
            h = pivot - 1
        } else {
            // if the pivot is equal to the target, return nums[pivot]
            return nums[pivot]
        }
    }

    return -1
}

func partition(nums []int, l, h int) int {
    high := nums[h]
    start := l

    for i := l; i < h; i++ {
        if nums[i] < high {
            // if nums[i] is less than high, then swap nums[start] with nums[i]
            nums[start], nums[i] = nums[i], nums[start]
            start++
        }
    }

    //swap nums[start] with nums[h]
    nums[start], nums[h] = nums[h], nums[start]

    return start
}

JavaScript-решение

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let n = nums.length;

    // if nums size is 1 return the first element
    if (n == 1) {
        return nums[0];
    }

    let l = 0, h = n - 1;

    // set target to n - k
    let target = n - k;

    while (l <= h) {
        // set pivot with the value returned by partition function
        let pivot = partition(nums, l, h);

        // if the pivot is less than the target, search the right side
        if (pivot < target) {
            l = pivot + 1;
        } else if (pivot > target) {
            // if the pivot is greater than the target, search the left side
            h = pivot - 1;
        } else {
            // if the pivot is equal to the target, return nums[pivot]
            return nums[pivot];
        }
    }

    return -1;
};

var partition = function(nums, l, h) {
    let high = nums[h];
    let start = l;

    for (let i = l; i < h; i++) {
        // if nums[i] is less than high, then swap nums[start] with nums[i]
        if (nums[i] < high) {
            [nums[start], nums[i]] = [nums[i], nums[start]];
            start++;
        }
    }

    //swap nums[start] with nums[h]
    [nums[start], nums[h]] = [nums[h], nums[start]];

    return start;
}

Пробный прогон

Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.

Input: nums = [3, 2, 1, 5, 6, 4]
       k = 2

// findKthLargest(vector<int>& nums, int k)
Step 1: n = nums.size()
          = 6

Step 2: if n == 0
           6 == 0
           false

Step 3: l = 0
        h = n - 1
          = 6 - 1
          = 5

        target = n - k
               = 6 - 2
               = 4

Step 4: loop while l <= h
          0 <= 5
          true

          pivot = partition(nums, l, h)
                = partition(nums, 0, 5)

// partition(nums, 0, 5)
Step 5: high = nums[h]
             = nums[5]
             = 4
        start = l
              = 0

        loop for i = l; i < h
          i < h
          0 < 5
          true

          if nums[i] < high
            nums[0] < 4
            3 < 4
            true

            swap(nums[start], nums[i])
            swap(nums[0], nums[0])
            nums = [3, 2, 1, 5, 6, 4]

            start++
            start = 1

            i++
            i = 1

        loop for i < h
          i < h
          1 < 5
          true

          if nums[i] < high
            nums[1] < 4
            2 < 4
            true

            swap(nums[start], nums[i])
            swap(nums[1], nums[1])
            nums = [3, 2, 1, 5, 6, 4]

            start++
            start = 2

            i++
            i = 2

        loop for i < h
          i < h
          2 < 5
          true

          if nums[i] < high
            nums[2] < 4
            1 < 4
            true

            swap(nums[start], nums[i])
            swap(nums[2], nums[2])
            nums = [3, 2, 1, 5, 6, 4]

            start++
            start = 3

            i++
            i = 3

        loop for i < h
          i < h
          3 < 5
          true

          if nums[i] < high
            nums[3] < 4
            5 < 4
            false

            i++
            i = 4

        loop for i < h
          i < h
          4 < 5
          true

          if nums[i] < high
            nums[4] < 4
            6 < 4
            false

            i++
            i = 5

        loop for i < h
          i < h
          5 < 5
          false

        swap(nums[start], nums[h])
        swap(nums[3], nums[5])
        swap(5, 4)
        nums = [3, 1, 2, 4, 6, 5]


        return start
        return 3

// findKthLargest(vector<int>& nums, int k)
Step 6: pivot = partition(nums, 0, 5)
              = 3

Step 7: if pivot < target
           3 < 4
           true

           l = pivot + 1
             = 3 + 1
             = 4

Step 8 loop while l <= h
         4 <= 5
         true

         pivot = partition(nums, l, h)
               = partition(nums, 4, 5)

// partition(nums, 4, 5)
Step 9: high = nums[h]
             = nums[5]
             = 5
        start = l
              = 4

        loop for i = l; i < h
          i < h
          4 < 5
          true

          if nums[i] < high
             nums[4] < 5
             6 < 5
             false

          i++
          i = 5

        loop for i < h
          5 < 5
          false

        swap(nums[start], nums[h])
        swap(nums[4], nums[5])
        swap(6, 5)

        nums = [3, 1, 2, 4, 5, 6]

        return start
        return 4

// findKthLargest(vector<int>& nums, int k)
Step 10: pivot = partition(nums, 4, 5)
               = 4

Step 11: if pivot < target
           4 < 4
           false
         else if pivot > target
           4 > 4
           false
         else
           return nums[4]
           return 5

We return the answer as 5.

Первоначально опубликовано на https://alkeshghorpade.me.