Javascript-форум (https://javascript.ru/forum/)
-   Элементы интерфейса (https://javascript.ru/forum/dom-window/)
-   -   Как правильно оптимизировать алгоритм сортировки? (https://javascript.ru/forum/dom-window/84621-kak-pravilno-optimizirovat-algoritm-sortirovki.html)

dc65k 31.10.2022 09:55

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

Задача:
Необходимо найти 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)?

ksa 31.10.2022 10:06

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

ksa 31.10.2022 10:17

Цитата:

Сообщение от 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)

voraa 31.10.2022 10:56

Цитата:

Сообщение от ksa
Достаточно просто по нему пройтись и найти минимальный или максимальный "элемент".

Надо найти n самых больших

ksa 31.10.2022 11:26

Тогда ждем уточнения... :D

dc65k 31.10.2022 13:12

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

Пример:
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]

рони 31.10.2022 14:24

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]

dc65k 31.10.2022 15:22

Спасибо. Но у меня вопрос был именно об оптимизации и не использовании метода .sort(), то есть стремление прийти к O(n).

Белый шум 31.10.2022 23:20

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

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]

dc65k 01.11.2022 16:55

Спасибо.


Часовой пояс GMT +3, время: 22:09.