Рассмотрим третью задачу из еженедельного конкурса Leetcode 334. Решения различных задач из других конкурсов вы можете найти здесь.
Найдите максимальное количество отмеченных индексов
Вам дан 0-индексированный массив целых чисел
nums
.
Изначально все индексы не отмечены. Вы можете выполнять эту операцию любое количество раз:
Выберите два разных непомеченных индекса
i
иj
так, чтобы было2 * nums[i] <= nums[j]
, затем отметьтеi
иj
.
Верните максимально возможное количество отмеченных индексов в
nums
, используя описанную выше операцию любое количество раз.
Решение
Давайте посмотрим на следующий пример:
Отсортированный массив будет выглядеть так:
Итак, у нас есть две половинки. Первый: [2,3] и Второй: [4,5]. Для 2 мы можем отметить как 4, так и 5, лучше отметить наименьшее число из второй половины, поэтому для 2 мы используем 4. Для 3 во второй половине нет пары, так как 2*3=6 › 5. Давайте рассмотрим один еще пример:
Мы можем разбить массив на 2 части: [4,5,6] и [8, 9,10]. Для 4 действительны все числа из второй половины. Для нас лучше выбрать самую маленькую, поэтому мы отметим 4 и 8. Для 5 мы не можем поставить 9 и можем поставить 10, поэтому мы отметим 5 и 10. Для 6 во второй половине нет действительной оценки.
Подход
Отсортируем массив и разделим его на две половины. Создадим 2 указателя first на первый элемент первой половины и second на первый элемент второй половины. Если 2*массив[первый] ≤ массив[второй]отметьте оба индекса и переместите первый и второй индексы к следующим элементам. Если нет, переместите второй индекс к следующему элементу.
Код
var maxNumOfMarkedIndices = function(nums) { nums.sort((a,b) => a - b) let first = 0 let endOfHalf = Math.floor(nums.length / 2) let second = endOfHalf let res = 0; while(first < endOfHalf && second< nums.length){ if(2*nums[first] <= nums[second]){ res+=2 first++ } second++ } return res };
Сложность
Временная сложность:O(N*Log(N))
Пространственная сложность:O(1)
P.S.
Вот мое решение на Leetcode.