Учитывая массив целых чисел 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-й самый большой элемент в массиве.
- Мы модифицируем пузырьковую сортировку, чтобы внешний цикл выполнялся не более K раз.
- В конце последнего цикла выведите 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-й самый большой элемент в массиве:
- Создайте минимальную кучу для первых k элементов массива: от nums[0] до nums[k — 1].
- Перебрать оставшиеся элементы от nums[k] до nums[n — 1].
- Сравните элемент массива с корнем кучи.
- Если элемент больше, чем корень, добавьте кучу, иначе ничего не делайте.
- После выполнения вышеуказанных шагов наша куча 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-й самый большой элемент в массиве:
- Перебрать массив и вставить элементы в очередь приоритетов.
- Если размер очереди превышает k, извлеките элемент из приоритетной очереди.
- После того, как мы выполнили итерацию по массиву, верните верхний элемент приоритетной очереди.
Фрагмент 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 самых больших элементов массива.
Нам необходимо выполнить следующие шаги:
- Создайте BST, перебирая элементы массива.
- Пройдите BST в обратном порядке K раз.
- Вернуть 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.