Различные подходы к решению Leetcode 347 в JavaScript
Есть бесчисленное множество способов подойти к этой проблеме и оптимизировать решение. В этой статье мы рассмотрим различные стратегии решения этой проблемы. Давайте сначала посмотрим на постановку задачи.
Постановка задачи:
Учитывая массив целых чисел
numsи целое числоk, вернуть наиболее часто встречающиеся элементыkнаиболее часто встречающиеся элементы. Вы можете вернуть ответ в любом порядке.
Эта проблема связана с числами и их частотами. Давайте погрузимся и посмотрим, как мы можем использовать наши навыки программирования, чтобы найти самые популярные цифры в массиве!
Подход 1: хэш-карта
- Переберите входной массив и подсчитайте частоту каждого элемента в хэш-карте.
- Отсортируйте значения карты в порядке убывания частоты каждого элемента.
- Сохраните верхние значения K в массиве результатов.
- Верните массив результатов.
// ES6 Arrow Function
const topKFrequent = (nums, k) => {
let map = new Map();
for(let i of nums) {
let count = map.get(i) || 0;
map.set(i, count + 1);
}
let i = 0,
result = [],
values = [...map.entries()].sort((a,b) => b[1] - a[1]);
while(i < k) {
result.push(values[i][0]);
i++;
}
return result;
};
Временная сложность:O(N Log(N))
Пространственная сложность:O(N)
Подход 2: сортировка ведра
В этом подходе мы используем карту для хранения частоты каждого элемента, а затем группируем элементы с одинаковой частотой в массив bucket. Наконец, он выполняет итерацию по массиву bucket в обратном порядке и извлекает из него k самых часто встречающихся элементов, которые возвращаются в качестве окончательного вывода.
- Создайте новый объект Map, массив bucket и массив result.
- Переберите входной массив nums и сохраните частоту каждого элемента в Map.
- Выполните итерацию по карте и сгруппируйте элементы с одинаковой частотой вместе в массиве bucket.
- Пройдитесь по массиву bucket в обратном порядке и поместите его элементы в массив result.
- Повторите шаг 4 k раз, чтобы получить k наиболее часто встречающихся элементов.
// ES6 Arrow Function
const topKFrequent = (nums, k) => {
let map = new Map();
let bucket = [], result = [];
for(let i of nums) {
let count = map.get(i) || 0;
map.set(i, count+1)
}
for(let [i, freq] of map) {
bucket[freq] = (bucket[freq] || new Set()).add(i);
}
for(let i = bucket.length - 1; i >= 0; i--) {
if(bucket[i]) result.push(...bucket[i]);
if(result.length >= k) break;
}
return result;
}
Временная сложность:O(N)
Пространственная сложность:O(N)
Подход 3: приоритетная очередь
- Постройте хеш-карту входного массива, где ключи — это элементы массива, а значения — их частоты. Вы можете использовать
Mapдля построения хеш-карты. - Создайте очередь с максимальным приоритетом двоичной кучи и поставьте в нее каждый элемент из хэш-карты. Приоритетом каждого элемента должна быть его частота.
- Удалите верхние
kэлементов из приоритетной очереди и поместите их в массив результатов. Вы можете использовать цикл, чтобы сделать этоkраз. - Вернуть массив результатов.
// ES6 Arrow Function
var topKFrequent = (nums, k) => {
let results = [];
let map = {};
nums.forEach(n => map[n] ? map[n] += 1 : map[n] = 1);
let pq = new PriorityQueue();
for(let key in map){
pq.enqueue(key, map[key]);
}
for(let i = 0; i < k; i++){
results.push(pq.dequeue());
}
return results;
};
Приоритетная очередь:
// ES6 Arrow Function
class Node {
constructor(val, priority){
this.val = val;
this.priority = priority;
}
}
class PriorityQueue {
constructor(){
this._values = [];
}
enqueue(val, priority){
this._values.push(new Node(val, priority));
this._traverseUp();
}
dequeue(){
const max = this._values[0];
const end = this._values.pop();
if(this._values.length > 0){
this._values[0] = end;
this._traverseDown();
}
return max.val;
}
_traverseUp(){
let idx = this._values.length - 1;
const el = this._values[idx];
while(idx > 0){
let pIdx = Math.floor((idx - 1) / 2);
let parent = this._values[pIdx];
if(el.priority <= parent.priority) break;
this._values[pIdx] = el;
this._values[idx] = parent;
idx = pIdx;
}
}
_traverseDown(){
let leftChildIdx = null;
let rightChildIdx = null;
let leftChild = null;
let rightChild = null;
let swapIdx = null;
let idx = 0;
const el = this._values[idx];
while(true){
swapIdx = null;
leftChildIdx = 2 * idx + 1;
rightChildIdx = 2 * idx + 2;
if(leftChildIdx < this._values.length){
leftChild = this._values[leftChildIdx];
if(leftChild.priority > el.priority){
swapIdx = leftChildIdx;
}
}
if(rightChildIdx < this._values.length){
rightChild = this._values[rightChildIdx];
if(
(swapIdx === null && rightChild.priority > el.priority) ||
(swapIdx !==null && rightChild.priority > leftChild.priority)
) {
swapIdx = rightChildIdx;
}
}
if(swapIdx === null) break;
this._values[idx] = this._values[swapIdx];
this._values[swapIdx] = el;
idx = swapIdx
}
}
}
Временная сложность:O(N log(K)), где n — количество элементов во входном массиве, а k — количество наиболее частых возвращаемых элементов.
Пространственная сложность:O(N + K), O(N) для хэш-карты и O(K) для приоритетной очереди.
И у вас есть это, ребята! Мы исследовали различные подходы, оптимизировали наши решения и, надеюсь, повеселились. Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!
Отзывы. Я хотел бы поблагодарить Алекса за ответ приоритетной очереди на leetcode. (Подход 3)
Проблема - Литкод 347
