10-10 leetcode 2009

链接 2009. Minimum Number of Operations to Make Array Continuous

题目

You are given an integer array nums. In one operation, you can replace any element in nums with any integer.

nums is considered continuous if both of the following conditions are fulfilled:

All elements in nums are unique.
The difference between the maximum element and the minimum element in nums equals nums.length - 1.
For example, nums = [4, 2, 5, 3] is continuous, but nums = [1, 2, 3, 5, 6] is not continuous.

Return the minimum number of operations to make nums continuous.

题解

这题核心的点在于数据连续的定义

元素唯一
最小值与最大值相差 nums.length - 1

元素唯一好解决，我们先 set 去重一下

那么最小值与最大值相差 nums.length - 1，怎么考虑

我们考虑将数组排序，然后遍历数组，对于每个元素符合的右侧的值 i + nums.length - 1，我们用二分来查找具体的位置。这样我们可以算出可以保留多少数，然后剩下的就是需要替换的数了。

import bisect


class Solution:
    def minOperations(self, nums: list[int]) -> int:
        length = len(nums)
        index = set(nums)
        nums = list(index)
        nums.sort()
        result = 10 ** 9 + 7
        for i, value in enumerate(nums):
            end = value + length - 1
            position = bisect.bisect_left(nums, end)
            if end in index:
                result = min(result, length - (position - i + 1))
            else:
                result = min(result, length - (position - i))
        return result

Comment