删除数对后的最小数组长度

标签: 贪心 数组 哈希表 双指针 二分查找 计数

难度: Medium

给你一个下标从 0 开始的 非递减 整数数组 nums 。

你可以执行以下操作任意次：

  • 选择 两个 下标 i 和 j ，满足 i < j 且 nums[i] < nums[j] 。
  • 将 nums 中下标在 i 和 j 处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。

请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的 最小 数组长度。

请注意，nums 数组是按 非降序 排序的。

示例 1：

输入：nums = [1,3,4,9]
输出：0
解释：一开始，nums = [1, 3, 4, 9] 。
第一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 1 < 3 。
删除下标 0 和 1 处的元素，nums 变成 [4, 9] 。
下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 4 < 9 。
删除下标 0 和 1 处的元素，nums 变成空数组 [] 。
所以，可以得到的最小数组长度为 0 。

示例 2：

输入：nums = [2,3,6,9]
输出：0
解释：一开始，nums = [2, 3, 6, 9] 。
第一次操作，我们选择下标 0 和 2 ，满足 nums[0] < nums[2] <=> 2 < 6 。
删除下标 0 和 2 处的元素，nums 变成 [3, 9] 。
下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 3 < 9 。
删除下标 0 和 1 处的元素，nums 变成空数组 [] 。
所以，可以得到的最小数组长度为 0 。

示例 3：

输入：nums = [1,1,2]
输出：1
解释：一开始，nums = [1, 1, 2] 。
第一次操作，我们选择下标 0 和 2 ，满足 nums[0] < nums[2] <=> 1 < 2 。
删除下标 0 和 2 处的元素，nums 变成 [1] 。
无法对数组再执行操作。
所以，可以得到的最小数组长度为 1 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • nums 是 非递减 数组。

Submission

运行时间: 40 ms

内存: 26.3 MB

class Solution:
    def minLengthAfterRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        x = nums[n // 2]
        max_cnt = bisect_right(nums, x) - bisect_left(nums, x)
        return max(max_cnt * 2 - n, n % 2)

Explain

此题解的核心思路在于找出数组中的中间值，并确定这个值的最大出现次数。由于数组是非递减的，这个中间值可以代表数组的中值或众数。题解利用这个中间值的最大出现次数，尝试将数组分成尽可能多的配对，每对满足较小数小于较大数的条件，从而使数组长度最小化。由于每次操作都会移除两个数字，所以解集中考虑了两种情况：1) 若最大出现次数乘以二小于数组长度，返回数组长度取模二的结果；2) 若不小于，则返回0或1，具体取决于数组长度是奇数还是偶数。这种方法有效地利用了数组的非递减特性，通过统计中间值的出现频率来最大化配对的可能。

时间复杂度: O(log n)

空间复杂度: O(1)

# 解法类定义
class Solution:
    # 主函数，计算最小数组长度
    def minLengthAfterRemovals(self, nums: List[int]) -> int:
        n = len(nums)  # 获取数组长度
        x = nums[n // 2]  # 获取数组的中间值
        # 用bisect模块找到中间值的范围
        max_cnt = bisect_right(nums, x) - bisect_left(nums, x)  # 计算中间值的出现次数
        # 返回最小数组长度，考虑到需要按配对删除的逻辑
        return max(max_cnt * 2 - n, n % 2)  # 结果取决于中间值出现次数和数组长度的关系

Explore

在非递减的数组中，中间值可以代表数组的中值或众数，这意味着它是数组中出现频率可能最高的一个元素。通过选择中间值作为关键元素，可以最大化可能的配对数，因为配对需要一个较小和一个较大的数，中间值的高频率增加了找到可配对元素的可能性。此外，选择中间值简化了实现，因为可以直接通过索引快速访问到它，并利用二分查找快速统计其出现次数。

该算法通过最大化配对的数目来最小化剩余数组的长度。选择中间值并统计其出现次数因其可能的高频率，使得配对的概率最大化。理论上，若中间值的出现次数较高，则可以与其他元素配对形成删除对，最大化删除操作的数量。当配对数最大化时，剩余未配对的元素数目自然最小。如果中间值的出现次数乘以二小于数组长度，意味着不能全部配对，剩余的元素数为数组长度的模二结果；如果不小于，则可能将所有元素配对完毕，剩余长度为0或1，取决于数组原始长度的奇偶性。

算法并没有具体指定删除哪些具体的元素对，而是依赖于中间值的出现次数来最大化可能的配对数。因为题解的核心在于统计中间值的出现频次，并尝试将其与其他元素配对，所以它不需要考虑具体的配对组合。算法的目标是通过最大化使用中间值的出现次数来减少数组长度，具体哪些元素被配对并未具体指明，这是一个理论上的最优化处理，实际上的实现可能需要具体的配对策略。

`max_cnt * 2 - n`计算的是使用中间值最大化配对后可能的剩余元素数量。如果`max_cnt * 2`小于`n`，这意味着即便所有中间值都能找到配对，仍有元素无法被配对，剩余元素数即为`n - max_cnt * 2`；如果`max_cnt * 2`大于等于`n`，理论上可以完全配对或最多剩下一个元素。`n % 2`用于处理数组长度为奇数的情况，因为奇数长度的数组无法完全配对，至少会剩下一个元素。这两个计算结合起来，允许算法在不同情况下给出最小的剩余数组长度。