What is the main pattern in Find the Maximum Number of Marked Indices?

The key pattern is binary search over the valid number of operations combined with greedy two-pointer pairing.

How do I check if k operations are possible?

Sort nums and pair the smallest k elements with the largest k elements using two pointers. If all satisfy 2 * nums[i] <= nums[j], k operations are feasible.

What is the time complexity for this approach?

Sorting takes O(n log n), and binary search with verification adds another O(n log n), giving O(n log n) overall.

Can I solve this without sorting?

Not efficiently. Sorting simplifies pairing and ensures the greedy two-pointer approach finds the maximum marked indices.

Are there edge cases to consider?

Yes. Arrays where no operation is possible return 0, and arrays where multiple pairs compete for the same indices must respect i < j and marking only once.

#2576

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

求出最多标记下标

给你一个下标从 0 开始的整数数组 nums 。一开始，所有下标都没有被标记。你可以执行以下操作任意次：选择两个互不相同且未标记的下标 i 和 j ，满足 2 * nums[i] ，标记下标 i 和 j 。请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。示例 1：输入…

数组双指针二分查找贪心排序

题目描述

给你一个下标从 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⁹

lightbulb

解题思路

方法一：贪心 + 双指针

根据题目描述，题目最多产生 $n / 2$ 组标记，其中 $n$ 为数组 $\textit{nums}$ 的长度。

为了将下标尽可能多地标记，我们可以将数组 $\textit{nums}$ 排序，接下来，我们遍历右半部分的每个元素 $\textit{nums}[j]$ ，用一个指针 $\textit{i}$ 指向左半部分的最小元素，如果 $\textit{nums}[i] \times 2 \leq \textit{nums}[j]$ ，则可以标记下标 $\textit{i}$ 和 $\textit{j}$ ，我们将 $\textit{i}$ 向右移动一个位置。继续遍历右半部分的元素，直到到达数组的末尾。此时，我们可以标记的下标数目为 $\textit{i} \times 2$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on pairing strategy and feasibility check for k operations.
question_mark
Check how candidates apply binary search to maximize marked indices.
question_mark
Listen for explanation of why greedy two-pointer pairing guarantees optimal answer.

warning

常见陷阱

外企场景

error
Failing to sort nums first, causing incorrect pairings.
error
Incorrectly pairing indices, violating i < j constraint or the 2*nums[i] <= nums[j] rule.
error
Not using binary search and trying brute-force, which is too slow for large arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change condition to 3 * nums[i] <= nums[j] and maximize marked indices.
arrow_right_alt
Restrict indices to be consecutive, altering the two-pointer strategy.
arrow_right_alt
Compute maximum marked indices but return the specific pairs chosen.

help

常见问题

外企场景

继续练习

#2234 花园的最大总美丽值 #2071 你可以安排的最多任务数目 #2563 统计公平数对的数目