Medium

题目描述

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

初始时，所有下标都未被标记。你可以执行以下操作任意次：

  • 选择两个 互不相同且未标记 的下标 i 和 j，满足 2 * nums[i] <= nums[j]，然后标记下标 i 和 j。

返回使用上述操作任意次后，nums 中最多可以标记的下标数目。

示例 1：

输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1，操作可以执行的原因是 2 * nums[2] <= nums[1]，即 2 * 2 <= 5。然后标记下标 2 和 1。
可以证明没有其他有效操作，所以答案是 2。

示例 2：

输入：nums = [9,2,5,4]
输出：4
解释：第一次操作中，选择 i = 3 和 j = 0，操作可以执行的原因是 2 * nums[3] <= nums[0]，即 2 * 4 <= 9。然后标记下标 3 和 0。
第二次操作中，选择 i = 1 和 j = 2，操作可以执行的原因是 2 * nums[1] <= nums[2]，即 2 * 2 <= 5。然后标记下标 1 和 2。
没有其他操作可以执行，所以答案是 4。

示例 3：

输入：nums = [7,6,8]
输出：0
解释：没有任何可以执行的有效操作，所以答案是 0。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

解题思路

这道题的核心思想是贪心匹配结合二分查找。

首先分析题目：我们需要找到满足 2 * nums[i] <= nums[j] 的配对，使配对数量最大化。为了最大化配对数量，我们应该：

  1. 排序数组：将数组从小到大排序，这样便于找到最优匹配策略。

  2. 贪心策略：对于每个较小的数，应该与能匹配的最小的较大数配对。具体来说：

    • 用最小的 k 个数与最大的 k 个数进行匹配
    • 第 i 个最小的数应该与第 (k-i+1) 个最大的数匹配

  3. 二分查找答案：我们可以二分查找最大的 k 值，使得能够成功进行 k 次配对操作。

  4. 验证函数：对于给定的 k，验证是否能进行 k 次配对：

    • 取前 k 个最小的数和后 k 个最大的数
    • 检查第 i 个最小数是否满足 2 * nums[i] <= nums[n-k+i]

这种方法的正确性在于：如果第 i 个最小数无法与第 (k-i+1) 个最大数配对，那么它也无法与更小的数配对，因此这种贪心策略是最优的。

代码实现

class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        auto canMark = [&](int k) -> bool {
            for (int i = 0; i < k; i++) {
                if (2 * nums[i] > nums[n - k + i]) {
                    return false;
                }
            }
            return true;
        };
        
        int left = 0, right = n / 2;
        int ans = 0;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (canMark(mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return ans * 2;
    }
};

class Solution:
    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        
        def can_mark(k):
            for i in range(k):
                if 2 * nums[i] > nums[n - k + i]:
                    return False
            return True
        
        left, right = 0, n // 2
        ans = 0
        
        while left <= right:
            mid = (left + right) // 2
            if can_mark(mid):
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return ans * 2

public class Solution {
    public int MaxNumOfMarkedIndices(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        
        bool CanMark(int k) {
            for (int i = 0; i < k; i++) {
                if (2 * nums[i] > nums[n - k + i]) {
                    return false;
                }
            }
            return true;
        }
        
        int left = 0, right = n / 2;
        int ans = 0;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (CanMark(mid)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return ans * 2;
    }
}

var maxNumOfMarkedIndices = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    
    const canMark = (k) => {
        for (let i = 0; i < k; i++) {
            if (2 * nums[i] > nums[n - k + i]) {
                return false;
            }
        }
        return true;
    };
    
    let left = 0, right = Math.floor(n / 2);
    let ans = 0;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (canMark(mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return ans * 2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(n log n)，其中排序需要 O(n log n)，二分查找需要 O(log n) 次，每次验证需要 O(n)，总体为 O(n log n)
空间复杂度O(1)，除了输入数组外只使用常数额外空间

相关题目