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

[dc65k]

Всем привет.

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

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

[ksa]

как оптимизировать алгоритм до 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]

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

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

[ksa]

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

[dc65k]

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

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

[рони]

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]

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

[Белый шум]

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

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]

Спасибо.