#javascript #mode
#javascript #режим
Вопрос:
Я пытаюсь получить любое число, которое является наиболее часто встречающимся числом в массиве, поэтому для массива, содержащего 1,2,10,5,1, результат должен быть равен 1. Код, который я написал, возвращает мне частоту для каждого числа, поэтому 1 встречается дважды, 2 встречается один раз, 10 встречается один раз и т.д. Есть предложения, как я могу исправить свой результат?
function mode(arr) {
var uniqNum = {};
var numCounter = function(num, counter) {
if(!uniqNum.hasOwnProperty(num)) {
uniqNum[num] = 1;
} else {
uniqNum[num] ;
}
};
arr.forEach(numCounter);
return uniqNum;
}
Комментарии:
1. Другая переменная и оператор if для отслеживания того, какое число лидирует? Кроме того, что вы хотите сделать, если два или более чисел имеют одинаковую частоту?
2. Если два или более чисел имеют самую высокую частоту, я бы хотел, чтобы каждое число, так что [1,2,1,2,3,4], я бы хотел, чтобы мой результат был 1,2.
Ответ №1:
Я сохранил ваш код без изменений и добавил несколько дополнительных операторов. Вот демонстрация: http://codepen.io/PiotrBerebecki/pen/rrdxRo
function mode(arr) {
var uniqNum = {};
var numCounter = function(num, counter) {
if(!uniqNum.hasOwnProperty(num)) {
uniqNum[num] = 1;
} else {
uniqNum[num] ;
}
};
arr.forEach(numCounter);
return Object.keys(uniqNum)
.sort((a,b) => uniqNum[b] - uniqNum[a]) // sort by frequency
.filter((val,ind,array) => uniqNum[array[0]] == uniqNum[val]) // leave only most frequent
.map(val => Number(val)); // convert text to number
}
console.log( JSON.stringify(mode([3,3,2,4,4])) ) // [3,4]
console.log( JSON.stringify(mode([2,4,3,3])) ) // [3] Ответ №2:
Я думаю, что это можно было бы сделать только с небольшой модификацией вашего forEach цикла и помощью другой вспомогательной структуры данных:
function mode(arr) {
var freq = [], uniqNum = {}, i;
arr.forEach(function (num) {
uniqNum[num] = i = (uniqNum[num] || 0) 1;
freq[i] = (freq[i] || []).concat(num);
});
return freq[freq.length - 1];
}
console.log(mode([1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 6, 7, 1, 6]));
Всего за одну итерацию по всем элементам массива мы можем собрать достаточно информации, чтобы распечатать результат:
uniqNumэто набор, который вы создали для сбора информации о частоте элемента.freqбудет массив, последний элемент которого будет содержать массив с элементами более высокой частоты.
Скрипка. Надеюсь, это поможет.
Комментарии:
1. умный ответ 🙂
2. Спасибо @LucasKot-Zaniewski и буду признателен за поддержку! Приветствия!
3. хотя массив частот 2d будет увеличиваться довольно быстро (в зависимости от вхождений), поэтому, безусловно, существует значительный компромисс, учитывая возможность увеличения входных массивов. Дал вам преимущество, но его стоит рассмотреть. Кроме того, вы не экономите так много времени, повторяя один раз вместо двух. Решение выглядит очень аккуратно.
4. Спасибо @LucasKot-Zaniewski! Массивы и объекты в JS действительно дешевы. Фактически, массив — это не что иное, как объект с дополнительным набором свойств, унаследованных Array.prototype . Если бы исходный массив был большим, повторение всех его элементов один раз определенно было бы быстрее, чем делать это дважды (некоторые ответы даже сортируют массив …). Я думаю, что также следует учитывать проблему пространства, но, с моей точки зрения, проблема времени возникнет раньше (массив должен быть огромным, чтобы столкнуться с проблемой пространства, и, вероятно, для завершения некоторых из предложенных алгоритмов потребуется много времени).
5. Полностью согласен с ненужной сортировкой. Я протестировал ваше решение против моего и думаю, что вы недооцениваете нагрузку на память вашей структуры данных. Я не думаю, что это работает так эффективно, как вы думаете. Но если вы мне не верите, проверьте тест в моем обновленном ответе 😉
Ответ №3:
Сначала мы хотим создать массив, в котором мы подсчитываем количество вхождений определенного значения до этого момента.
Затем мы используем функцию reduce для возврата массива значений, считанных из исходного массива для индексов, значения которых имеют текущее максимальное отображение. Мы переопределяем max и очищаем конечный выходной массив режимов (если установлен новый max) по мере продвижения. Мы хотим, чтобы это была коллекция на случай, если есть связь для максимального появления.
Дополнительным преимуществом приведенного ниже является то, что он не требует сортировки, которая является более дорогостоящей o (nlog n) и снижает временную сложность до линейной. Я также хотел, чтобы используемые функции были сведены только к двум (map и reduce), поскольку это все, что нужно в этом случае.
редактировать: исправлена серьезная ошибка uniqNum [e] = 1 вместо uniqNum [e] 1, которая осталась незамеченной, поскольку мой первоначальный массив case все еще возвращал ожидаемый результат. Также синтаксис стал более кратким в пользу большего количества комментариев.
var arr = [1,2,10,5,1,5,2,2,5,3,3];
//global max to keep track of which value has most appearances.
var max = -1;
var uniqNum = {};
var modeArray = arr.map(function(e) {
//create array that counts appearances of the value up to that point starting from beginning of the input arr array.
if(!uniqNum.hasOwnProperty(e)) {
uniqNum[e] = 1;
return 1;
} else {
return uniqNum[e] = 1;
}
//reduce the above appearance count array into an array that only contains values of the modes
}).reduce(function (modes, e1, i) {
//if max gets beaten then redefine the mode array to only include the new max appearance value.
if(e1 > max){
//redefining max
max = e1;
//returning only the new max element
return [arr[i]];
//if its a tie we still want to include the current value but we don't want to empty the array.
}else if(e1 == max){
//append onto the modes array the co-max value
return[...modes, arr[i]];
}
return modes;
},[]);
alert(modeArray); Вот тест, который вы можете выполнить для моего решения против @acontell. В моем браузере (Chrome с V8) мое решение было примерно в три-четыре раза быстрее для массивов с большим количеством повторяющихся значений и еще большим преимуществом для дистрибутивов с меньшим количеством повторяющихся значений. @acontell’s, безусловно, является более чистым решением, но определенно не быстрее в исполнении.
var arr = [];
for(var i=0; i < 100000; i ){
arr.push(Math.floor(Math.random() * (100 - 1)) 1);
}
console.time("test");
test();
function test(){
var max = -1;
var uniqNum = {};
var modeArray = arr.map(function(e) {
//create array that counts appearances of the value up to that point starting from beginning of the input arr array.
if(!uniqNum.hasOwnProperty(e)) {
uniqNum[e] = 1;
return 1;
} else {
return uniqNum[e] = 1;
}
//reduce the above appearance count array into an array that only contains values of the modes
}).reduce(function (modes, e1, i) {
//if max gets beaten then redefine the mode array to only include the new max appearance value.
if(e1 > max){
//redefining max
max = e1;
//returning only the new max element
return [arr[i]];
//if its a tie we still want to include the current value but we don't want to empty the array.
}else if(e1 == max){
//append onto the modes array the co-max value
modes.push(arr[i])
return modes;
}
return modes;
},[]);
}
console.timeEnd("test");
console.time("test1");
test1();
function test1 () {
var freq = [],
uniqNum = {},
i;
arr.forEach(function(num) {
uniqNum[num] = i = (uniqNum[num] || 0) 1;
freq[i] = (freq[i] || []).concat(num);
});
return freq[freq.length - 1];
}
console.timeEnd("test1"); Комментарии:
1. Вы заслуживаете повышения, молодец! Я постараюсь проверить это завтра (сегодня нет времени).
Ответ №4:
Я попытался в качестве упражнения решить эту проблему с помощью собственных функций js.
var arr = [1,2,10,5,1];
// groupBy number
var x = arr.reduce(
function(ac, cur){
ac[cur]?(ac[cur] = ac[cur] 1):ac[cur] = 1;
return ac;
}, {}
);
// sort in order of frequencies
var res = Object.keys(x).sort(
function(a,b){ return x[a] < x[b]}
);
res[0] has the most frequent element
Комментарии:
1. Ваша строка
ac[cur]?(ac[cur] = ac[cur] 1):ac[cur] = 1;может быть отсортирована поac[cur] = (ac[cur] || 0) 1;