Вам дают целочисленный массив Nums и целое число k .
В одной операции вы можете выбрать два числа из массива, сумма которой равен k и удалить их из массива.
Вернуть максимальное количество операций, которые вы можете выполнить на массиве.
Пример 1:
Input: nums = [1,2,3,4], k = 5 Output: 2 Explanation: Starting with nums = [1,2,3,4]: - Remove numbers 1 and 4, then nums = [2,3] - Remove numbers 2 and 3, then nums = [] There are no more pairs that sum up to 5, hence a total of 2 operations.
Пример 2:
Input: nums = [3,1,3,4,3], k = 6 Output: 1 Explanation: Starting with nums = [3,1,3,4,3]: - Remove the first two 3's, then nums = [1,4,3] There are no more pairs that sum up to 6, hence a total of 1 operation.
Ограничения:
1 длиной1 [я]1
Тесты
Ссылка на код
import pytest
from .Day18_MaxNumberOfKSumPairs import Solution
s = Solution()
@pytest.mark.parametrize(
"nums,k,expected",
[
([1, 2, 3, 4], 5, 2),
([3, 1, 3, 4, 3], 6, 1),
([3, 5, 1, 5], 2, 0),
([4, 4, 1, 3, 1, 3, 2, 2, 5, 5, 1, 5, 2, 1, 2, 3, 5, 4], 2, 2),
],
)
def test_max_operations(nums, k, expected):
assert s.maxOperations(nums, k) == expected
Решение
Ссылка на код
from typing import List
import math
class Solution:
def maxOperations(self, nums: List[int], k: int) -> int:
max_ops = 0
counts = {}
for n in nums:
if n in counts:
counts[n] = counts[n] + 1
else:
counts[n] = 1
for n in counts:
diff = k - n
if diff in counts and counts[diff] > 0:
ops = 0
if n == k // 2:
ops = math.floor(counts[n] // 2)
else:
ops = min(counts[n], counts[diff])
max_ops += ops
counts[diff] = counts[diff] - ops
counts[n] = counts[n] - ops
return max_ops
Анализ
Комментарий
Довольно легкий и быстрый сегодня. Я мог бы определенно улучшить это, но это сделает.
Во время выполнения есть На) . Мы получили список один раз, чтобы вставить на карту. Затем мы проходим на карте ключи и сделаем наши расчеты. Пространство это На) Потому что мы создали карту для хранения отсчетов.
Использование карты дает нам очень быстрый способ посмотреть k - n для каждого n . Если мы найдем матч, мы можем уменьшить количество подсчетов для каждого номера в матче Мин (счетчики [n], считает [diff]) и увеличивайте максимальные операции этим номером.
Другим дел нам нужно думать о том, где k - n является K/2 Отказ Это сломает нашу реализацию, поэтому нам нужно добавить чек на этот случай и использовать math.floor (счетчики [n]//2) Отказ Например, возьмите к и [1, 1, 1, 1] Отказ Если мы использовали Мин (счетчики [n], считает [diff]) Мы получили 4 Но правильный ответ будет 2 Что мы получаем от math.floor (счетчики [n]//2) Отказ
Оригинал: “https://dev.to/ruarfff/day-18-max-number-of-k-sum-pairs-2dig”