Пошаговое объяснение
Проблема большинства элементов имеет, на мой взгляд, несколько странное, чересчур сложное направление:
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; }
Спасибо за чтение!
И помните: твердость › талант.