Рассмотрим третью задачу из еженедельного конкурса 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.