求出最多标记下标

难度: 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 和 1 。
没有其他更多可执行的操作，所以答案为 2 。

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Submission

运行时间: 108 ms

内存: 30.0 MB

class Solution:
    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        i = 0
        for x in nums[(n+1)//2:]:
            if nums[i] * 2 <= x:
                i += 1
        return i * 2

Explain

此题解采用排序加贪心的方法来解决问题。首先对数组 nums 进行排序，这样更容易找到满足 2 * nums[i] <= nums[j] 的 i 和 j。由于数组已排序，对于较小的元素，我们需要寻找后半部分中首个满足条件的较大元素。算法从数组的中点开始向后遍历，尝试找到与前半部分的元素 i 形成合法对的元素 j。如果找到了，i 指针向前移动，表示我们标记了一对下标。由于每次操作标记两个下标，所以返回的是成功匹配的对数乘以 2。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def maxNumOfMarkedIndices(self, nums: List[int]) -> int:
        nums.sort()  # 对数组进行排序
        n = len(nums)  # 数组长度
        i = 0  # 初始化 i 指针，用于前半部分的索引
        # 从中点开始遍历至数组末尾
        for x in nums[(n+1)//2:]:
            # 检查是否存在满足条件的对
            if nums[i] * 2 <= x:
                i += 1  # 找到合适的 j 后，i 指针向前移动
        return i * 2  # 返回标记的下标数，每对贡献两个下标

Explore

直接遍历整个数组来查找符合条件的下标对需要O(n^2)的时间复杂度，因为每个元素都需要与其他所有元素进行比较。通过先排序数组，可以利用数组的有序性，使用双指针方法来降低时间复杂度到O(n log n)（排序的时间复杂度），之后利用双指针线性遍历数组来找到符合条件的下标对，这样整体效率更高。

在本题的上下文中，目标是找到最多的满足条件的下标对的数量，而不是具体的下标位置。因此，改变原始数组的下标顺序对结果的数目没有影响。如果需要原始下标，可以在排序前存储每个元素的原始下标，然后在找到对应下标对后再映射回原数组的下标。

从数组的中点开始遍历是基于问题条件 2 * nums[i] <= nums[j] 的特性。排序后的数组是递增的，因此较小的元素在数组的前半部分，较大的元素在后半部分。从中点开始向后遍历可以更快地找到满足条件的 j。如果从头开始遍历，对于每个 i，可能需要遍历多个 j 才能找到满足条件的第一个 j，这样会增加不必要的计算和时间复杂度。

算法通过排序保证数组是有序的，然后利用双指针策略，其中一个指针 i 从前半部分开始，另一个指针从中点开始向后寻找 j。由于数组已排序，一旦找到满足 2 * nums[i] <= nums[j] 的 j，就可以确定这是对于当前 i 来说最左边（也就是最优的）满足条件的 j。因此，算法每次都能为每个 i 找到最优的 j，从而保证结果的正确性。