Найти второй по частоте элемент из массива целых чисел? - PullRequest
Новая
       91

Найти второй по частоте элемент из массива целых чисел?

1 голос
/ 13 июля 2020

Я ищу ответ на проблему кодирования в JavaScript, на которой я застрял, вот вопрос:

Напишите функцию, которая принимает массив целых чисел и возвращает элемент этого массива.

Функция должна определять частоту каждого элемента (сколько раз элемент появляется в массиве) и, когда это возможно, должна возвращать элемент со второй по величине частотой. В противном случае он должен возвращать целое число с наименьшей частотой.

Если существует более одного элемента, удовлетворяющего требованиям, то должен быть возвращен второй наименьший (согласно значению).

Примеры выходных данных:

secondLowest ([4, 3, 1, 1, 2]) === 1

secondLowest ([4, 3, 1, 1, 2, 2]) === 2

secondLowest ([4, 3, 1, 2]) === 2

Это то, что у меня есть, хотя я не знаю, как лучше go об ответе после этого: 


    function mode(array) {
  if (array.length == 0) return null;
  let modeMap = {};
  let maxEl = array[0],
    maxCount = 1;
  for (let i = 0; i < array.length; i++) {
    var el = array[i];
    if (modeMap[el] == null) modeMap[el] = 1;
    else modeMap[el]++;
    if (modeMap[el] > maxCount) {
      maxEl = el;
      maxCount = modeMap[el];
    }
  }
  return maxEl;
}

1 Ответ

1 голос
/ 13 июля 2020

Я был полон решимости дать общую c параметризованную функцию, где номер не жестко запрограммирован.

В вашем примере используются два жестко запрограммированных значения:

  • секунда должна быть выбрана минимальная частота
  • В случае ничьей следует выбрать значение второе наименьшее

Следующий код работает следующим образом:

  • Получить частоту каждого входного значения
  • Сгруппировать вместе все значения с одинаковой частотой.
  • Отсортируйте эти сгруппированные пары по частоте и выберите n-е наименьшее (в вашем case, n=2)
  • Если n-я самая низкая частота имеет несколько пар, отсортируйте эти пары по значению и выберите m-ю самую низкую пару (в вашем случае m=2)
  • Возвращает значение этой последней пары

Параметры m и n, на которые я здесь ссылаюсь, в коде называются freqInd и valInd. Обратите внимание, что для выбора второй самой низкой частоты freqInd должно быть 1, а не 2 (поскольку 0 выберет самую низкую частоту, и, следовательно, 1 выберет вторую самую низкую). 

let lowestFreqVal = (freqInd, valInd, values) => {
  
  // Calculate frequencies in a map
  let f = new Map();
  for (let v of values) f.set(v, (f.get(v) || 0) + 1);
  
  // Group together all val/freq pairs with the same frequency
  let ff = new Map();
  for (let [ val, freq ] of f) ff.set(freq, (ff.get(freq) || []).concat([ val ]));
  
  // Sort these groups by frequency
  let byFreq = [ ...ff ].sort(([ freq1 ], [ freq2 ]) => freq1 - freq2);  
  
  // Here are all the items of the `freqInd`-th lowest frequency, sorted by value
  // Note that `[1]` returns an array of integers at the frequency, whereas `[0]` would return the frequency itself
  let lowestItems = byFreq[ Math.min(byFreq.length - 1, freqInd) ][1]
    .sort((v1, v2) => v1 - v2);
  
  // Return the `valInd`-th lowest value
  return lowestItems[ Math.min(lowestItems.length - 1, valInd) ];
  
};

console.log('Some random examples:');
for (let i = 0; i < 10; i++) {
  // An array of random length, full of random integers
  let arr = [ ...new Array(3 + Math.floor(Math.random() * 5)) ]
    .map(v => Math.floor(Math.random() * 4));
  
  // Show the result of `lowestFreqVal` on this random Array
  console.log(`lowestFreqVal(1, 1, ${JSON.stringify(arr)}) = ${lowestFreqVal(1, 1, arr)}`);
}

Это не оптимальное решение, так как используется sort. Известно, что проблема нахождения некоторого n-го максимального значения в списке может быть реализована для обеспечения лучшего времени выполнения, чем sort (и значительно лучшего времени выполнения, когда n является небольшим значением - мы можем видеть это интуитивно, потому что если n=0, единственный проход (O(n)) делает свое дело).

...