Medium

题目描述

给定一个按非递减顺序排序的整数数组 nums。

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

  • 选择两个下标 i 和 j，其中 nums[i] < nums[j]。
  • 然后，从 nums 中移除下标 i 和 j 处的元素。剩余元素保持原有顺序，数组重新编号。

返回执行零次或多次操作后 nums 的最小长度。

示例 1：

输入：nums = [1,2,3,4]
输出：0
解释：可以移除所有元素对。

示例 2：

输入：nums = [1,1,2,2,3,3]
输出：0
解释：可以移除所有元素对。

示例 3：

输入：nums = [1000000000,1000000000]
输出：2
解释：由于两个数字相等，无法移除。

示例 4：

输入：nums = [2,3,4,4,4]
输出：1
解释：可以移除4对元素，剩余1个。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums 按非递减顺序排序

解题思路

解题思路

这是一个贪心问题，关键在于如何最大化移除的元素对数。

基本观察： 要最大化移除操作次数，应该选择最小的k个元素和最大的k个元素进行配对。因为：

  1. 小元素更容易与大元素形成有效配对（满足 nums[i] < nums[j]）
  2. 这样的策略能够最大化可配对的数量

核心思路： 设我们要进行k次移除操作，那么：

  • 选择最小的k个元素：nums[0], nums[1], …, nums[k-1]
  • 选择最大的k个元素：nums[n-k], nums[n-k+1], …, nums[n-1]
  • 将第i小的元素与第i大的元素配对

有效配对的条件： 对于每个i ∈ [0, k-1]，必须满足 nums[i] < nums[n-k+i]

算法步骤：

  1. 使用二分查找找到最大的有效k值
  2. 答案为 n - 2*k（总长度减去移除的元素个数）

优化思路： 也可以直接统计出现次数最多的元素频率maxFreq，答案为max(0, 2*maxFreq - n)。这是因为当某个元素出现次数超过一半时，多余的部分无法配对移除。

代码实现

class Solution {
public:
    int minLengthAfterRemovals(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n / 2;
        
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid - 1] < nums[n - mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return n - 2 * left;
    }
};

class Solution:
    def minLengthAfterRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = 0, n // 2
        
        while left < right:
            mid = left + (right - left + 1) // 2
            if nums[mid - 1] < nums[n - mid]:
                left = mid
            else:
                right = mid - 1
        
        return n - 2 * left

public class Solution {
    public int MinLengthAfterRemovals(IList<int> nums) {
        int n = nums.Count;
        int left = 0, right = n / 2;
        
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid - 1] < nums[n - mid]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        
        return n - 2 * left;
    }
}

var minLengthAfterRemovals = function(nums) {
    const n = nums.length;
    let left = 0, right = Math.floor(n / 2);
    
    while (left < right) {
        const mid = left + Math.floor((right - left + 1) / 2);
        if (nums[mid - 1] < nums[n - mid]) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    
    return n - 2 * left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(log n)
空间复杂度O(1)

相关题目