Как правильно оптимизировать алгоритм сортировки?
Всем привет.
Задача: Необходимо найти 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)? |
dc65k, для нахождения максимального или минимального не обязательно сортировать массив.
Достаточно просто по нему пройтись и найти минимальный или максимальный "элемент". |
Цитата:
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) |
Цитата:
|
Тогда ждем уточнения... :D
|
Не об этом же речь.
Пример: 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] |
Спасибо. Но у меня вопрос был именно об оптимизации и не использовании метода .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] |
Спасибо.
|
Часовой пояс GMT +3, время: 22:09. |