Пошаговое объяснение

Проблема большинства элементов имеет, на мой взгляд, несколько странное, чересчур сложное направление:

Return the majority element of an array, which is the element that appears more than ⌊ n/2 ⌋ times.

Я не знаю о необходимости вычисления того, какой элемент появляется более чем в 50% случаев. Мой подход был немного проще и интуитивнее: задача называется «элемент большинства», поэтому давайте просто найдем элемент, который чаще всего встречается в массиве, и вернем его. Приступим к делу.

Допустим, у нас есть массив с именем nums, который выглядит так: [3, 2, 3]. Ясно, что 3 появляется больше всего, и это то, что нам нужно вернуть. Как мы делаем это в коде?

Несколько вещей, о которых следует помнить, когда мы разрабатываем решение:

  • Чтобы узнать, какой элемент отображается чаще всего, нам придется перебрать весь массив. Обойти это просто невозможно.
  • Нам нужно будет вычислить количество путей, сколько существует каждого элемента, и вернуться к этому счетчику позже, чтобы узнать, какой из них является наиболее часто летающим в нашем массиве.

Таким образом, итерация и хэш-карты хорошо помогают решить эту проблему.

Во-первых, давайте объявим нашу функцию с пустым объектом (также известным как хеш-карта) и счетчиком частоты:

function majorityElement(nums) {
  let numsObj = {};
  let maxFreq = 0;
}

Как уже упоминалось, нам нужно повторить. Пока мы итерируем, давайте заполним наше хранилище объектов numsObj key:value, следуя следующему правилу: для каждого элемента, который вы видите, создайте ключ со значением 1, если вы не видели его раньше, и в этом случае , просто добавьте 1 к его значению.

Таким образом, когда мы перебираем наш входной массив, в конце у нас будет аккуратно организованный объект, который будет иметь всю необходимую нам информацию: какие элементы находятся в массиве и сколько раз он появляется. Для нашего примера numsObj будет выглядеть так:

numsObj = {
   2: 1,
   3: 2
}

Далее нам нужно пройти через наш numsObj, проверяя значения каждого ключа, то есть частоту появления каждого числа в массиве. Делая это, мы должны спросить: больше ли это значение, чем maxFreq, которое я видел на данный момент? Если это так, я должен установить maxFreq на это значение. И пока мы это делаем, мы должны держаться за то число, которое появляется чаще всего. Вот что делает этот фрагмент кода:

for (num in numsObj) {
    if (numsObj[num] > maxFreq) {
      maxFreq = numsObj[num];
      maxElement = parseInt(num);
    }
  }

В нашем примере мы сначала итерируем число 2, которое появляется один раз. 1 больше, чем текущее значение maxFreq, равное 0, при котором оно было инициализировано? Конечно. Поэтому мы устанавливаем для maxFreq значение 1, а для maxElement значение 2. Обратите внимание на функцию parseInt(). Это просто преобразование ключа в объекте обратно в число, чтобы пройти тесты.

На следующей итерации число, которое мы видим, равно 3. Мы ищем 3 в нашем хэше numsObj, чтобы увидеть его значение. Мы видим, что это 2. Мы сравниваем 2 с maxFreq в операторе if. Поскольку 2 больше, чем текущее значение 1, оператор if снова оценивается как true, устанавливает MaxFreq равным 2, а maxElement равным 3.

Мы завершили итерацию по нашему хэшу numsObj, и теперь осталось только вернуть maxElement: 3. Вот полный код:

function majorityElement(nums) {
  let numsObj = {};
  let maxFreq = 0;
  let maxElement = null;
for (let num of nums) {
    numsObj[num] = numsObj[num] + 1 || 1;
  }
for (num in numsObj) {
    if (numsObj[num] > maxFreq) {
      maxFreq = numsObj[num];
      maxElement = parseInt(num);
    }
  }
  return maxElement;
}

Спасибо за чтение!

И помните: твердость › талант.