Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 31.10.2022, 09:55
Аспирант
Отправить личное сообщение для dc65k Посмотреть профиль Найти все сообщения от dc65k
 
Регистрация: 19.05.2020
Сообщений: 46

Как правильно оптимизировать алгоритм сортировки?
Всем привет.

Задача:
Необходимо найти n самых частых вхождений в массиве.

Решение:
const array = [9, 9, 9, 9, 8, 8, 4, 4, 4, 1, 2];

const getN = (array, n) => {

    const obj = array.reduce((acc, c) => {
        acc[c] ? acc[c] += 1 : acc[c] = 1;
        return acc
    }, {})

    return Object.keys(obj).sort((a, b) => {
        return obj[b] - obj[a];
    }).slice(0, n).map((el) => parseInt(el));
}

console.log(getN(array, 2)); // [9, 4]


Подскажите, как оптимизировать алгоритм до O (n), и не использовать. sort() O (n log2n)?
Ответить с цитированием
  #2 (permalink)  
Старый 31.10.2022, 10:06
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 14,118

dc65k, для нахождения максимального или минимального не обязательно сортировать массив.
Достаточно просто по нему пройтись и найти минимальный или максимальный "элемент".
Ответить с цитированием
  #3 (permalink)  
Старый 31.10.2022, 10:17
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 14,118

Сообщение от dc65k
как оптимизировать алгоритм до O (n), и не использовать. sort()
Как вариант...
const a = [9, 9, 9, 9, 8, 8, 4, 4, 4, 1, 2]
const o = a.reduce((o, v) => {
	o.list[v] = (o.list[v] ?? 0) + 1
	if (o.list[v] > o.max) o.max = o.list[v]
	return o
}, {list: {}, max: 0})
alert(o.max)
Ответить с цитированием
  #4 (permalink)  
Старый 31.10.2022, 10:56
Аватар для voraa
Профессор
Отправить личное сообщение для voraa Посмотреть профиль Найти все сообщения от voraa
 
Регистрация: 03.02.2020
Сообщений: 2,692

Сообщение от ksa
Достаточно просто по нему пройтись и найти минимальный или максимальный "элемент".
Надо найти n самых больших
Ответить с цитированием
  #5 (permalink)  
Старый 31.10.2022, 11:26
Аватар для ksa
ksa ksa вне форума
CacheVar
Отправить личное сообщение для ksa Посмотреть профиль Найти все сообщения от ksa
 
Регистрация: 19.08.2010
Сообщений: 14,118

Тогда ждем уточнения...
Ответить с цитированием
  #6 (permalink)  
Старый 31.10.2022, 13:12
Аспирант
Отправить личное сообщение для dc65k Посмотреть профиль Найти все сообщения от dc65k
 
Регистрация: 19.05.2020
Сообщений: 46

Не об этом же речь.

Пример:
const array = [9, 9, 9, 9, 8, 8, 4, 4, 4, 1, 2]; // [9, 4]
console.log(getN(array, 2)); // [9, 4]

const array2 = [1, 1, 1, 2, 2, 3, 3, 3,]; // [1, 3]
console.log(getN(array, 2)); // [1, 3]

const array3 = [5, 5, 5, 9, 8, 9, 1, 1, 1, 1]; // [1, 5, 9]
console.log(getN(array, 3)); // [1, 5, 9]
Ответить с цитированием
  #7 (permalink)  
Старый 31.10.2022, 14:24
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,064

dc65k,
const getN = (array, n) => {

    const obj = array.reduce((acc, c) => {
        acc[c] = (acc[c] || 0) + 1;
        return acc
    }, {})

    return [...new Set(array)].sort((a, b) => {
        return obj[b] - obj[a];
    }).slice(0, n);
}

const array = [9, 9, 9, 9, 8, 8, 4, 4, 4, 1, 2]; // [9, 4]
console.log(getN(array, 2)); // [9, 4]

const array2 = [1, 1, 1, 2, 2, 3, 3, 3,]; // [1, 3]
console.log(getN(array2, 2)); // [1, 3]

const array3 = [5, 5, 5, 9, 8, 9, 1, 1, 1, 1]; // [1, 5, 9]
console.log(getN(array3, 3)); // [1, 5, 9]
Ответить с цитированием
  #8 (permalink)  
Старый 31.10.2022, 15:22
Аспирант
Отправить личное сообщение для dc65k Посмотреть профиль Найти все сообщения от dc65k
 
Регистрация: 19.05.2020
Сообщений: 46

Спасибо. Но у меня вопрос был именно об оптимизации и не использовании метода .sort(), то есть стремление прийти к O(n).
Ответить с цитированием
  #9 (permalink)  
Старый 31.10.2022, 23:20
Аватар для Белый шум
Профессор
Отправить личное сообщение для Белый шум Посмотреть профиль Найти все сообщения от Белый шум
 
Регистрация: 19.01.2012
Сообщений: 498

Не знаю насколько оптимально, но без сортировки:

const array = [9, 9, 9, 9, 8, 8, 4, 4, 4, 1, 2];
 
const getN = (array, n) => {
    let acc={}, arr=[];
    array.forEach( c => {
        acc[c] ? acc[c] += 1 : acc[c] = 1;
        arr[ acc[c] ] ? arr[ acc[c] ].push(c) : arr[ acc[c] ] = [c];
    } );

    for( let i=arr.length - 1; i>1; i-- ) {
        if( arr[i].length >= n ) return arr[i];
    }    
    return arr[1];
}
 
console.log(getN(array, 2)); // [9, 4]
console.log(getN([1, 1, 1, 2, 2, 3, 3, 3,], 2)) // [1, 3]
console.log(getN([5, 5, 5, 9, 8, 9, 1, 1, 1, 1], 3)); // [1, 5, 9]

Последний раз редактировалось Белый шум, 31.10.2022 в 23:40.
Ответить с цитированием
  #10 (permalink)  
Старый 01.11.2022, 16:55
Аспирант
Отправить личное сообщение для dc65k Посмотреть профиль Найти все сообщения от dc65k
 
Регистрация: 19.05.2020
Сообщений: 46

Спасибо.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как правильно подключить стили в webpack? s24344 Сборка проекта, утилиты 0 08.11.2018 09:00
Как правильно подключаться к внешнему JSON MC-XOBAHCK Общие вопросы Javascript 3 14.02.2018 19:30
Как написать алгоритм выборки в javascript? Isaac Общие вопросы Javascript 13 06.02.2013 11:15
Как правильно прицепить обработку события slowklg Events/DOM/Window 6 15.03.2012 16:20
Как правильно очистить maxlength в input? Маэстро Events/DOM/Window 10 22.06.2011 18:14