目标
给你一个下标从 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^5
- 1 <= nums[i] <= 10^9
提示：
- Think about how to check that performing k operations is possible.
- To perform k operations, it’s optimal to use the smallest k elements and the largest k elements and think about how to match them.
- It’s optimal to match the ith smallest number with the k-i + 1 largest number.
- Now we need to binary search on the answer and find the greatest possible valid k.
思路
有一个数组 nums，每一次操作我们可以标记数组中未被标记的两个数，要求其中一个数的两倍小于等于另一个数。问经过任意次操作，最多可以标记多少个数。
题目与下标无关，可以先排序。使用双指针 l r 从前往后找到第一个大于等于其两倍的数 p。然后 l+1 r 继续向后搜索，直到 l 到达 p，这时将 应该使用一个数组记录是否已标记，当 l 赋值为 r，并且赋值 r = r + 1，继续前面的算法。l 第一次到达 p 时，应跳转到之前 r 未被标记的下标。
这种贪心策略也是不对的，对于示例2，排序后的数组为 2 4 5 9。如果优先标记 2 4 后面就不能再标记了，而如果先标记 2 5 我们还可以标记 4 9。
那如果我们倒过来考虑呢？从后往前找试试。反过来也不对，例如 10 10 40 100 如果先标记 40 100 前面就不能再标记了。
这样一来我们不知道满足条件后是否应该标记，需要搜索解空间看看哪个最大。回溯搜索相当于搜索n叉树 O(n^n)，如果不进行剪枝或者记忆的话肯定超时。如果考虑动态规划，状态又比较多，取决于元素是否被标记。
看了提示，匹配策略一定是前 k 个小的 small[i] 与后 k 个大的 big[i] 匹配。还是上面的例子 2 4 | 5 9 10 10 | 40 100 最优的匹配方式就是 2 5 4 9 10 40 10 100。现在问题就变成了找出最大的 k。使用二分法查找满足条件的最大 k，然后返回 2k 就是答案。
这道题卡住的点是没想清楚匹配方式。先入为主地以滑动窗口的方式匹配，连续地比较，匹配第一个能够匹配的，这种策略是不对的。
更优的解法是直接用双指针遍历，因为二分查找的判断复杂度为O(k)，整体是O(klogn)，不如双指针的O(n)。
代码
/**
* @date 2024-09-12 9:14
*/
public class MaxNumOfMarkedIndices2576 {
/**
* 排序的复杂度O(nlogn) 双指针匹配的复杂度O((n + 1) / 2)
*/
public int maxNumOfMarkedIndices_v1(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int rs = (n + 1) / 2;
int l = 0;
for (int r = rs; r < n; r++) {
if (nums[l] * 2 <= nums[r]) {
l++;
}
}
return 2 * l;
}
/**
* 排序的复杂度O(nlogn) 二分查找复杂度O(klogn) 其中判断的复杂度O(k) k最坏的情况下取n/2
*/
public int maxNumOfMarkedIndices(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int l = 0, r = n / 2, k = l + (r - l) / 2;
while (l <= r) {
if (check(nums, k)) {
l = k + 1;
} else {
r = k - 1;
}
k = l + (r - l) / 2;
}
return 2 * r;
}
public boolean check(int[] nums, int k) {
int n = nums.length;
for (int i = 0; i < k; i++) {
if (nums[i] * 2 > nums[n - k + i]) {
return false;
}
}
return true;
}
}
性能
二分查找
双指针
