2576.求出最多标记下标

目标

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

}

性能

二分查找

双指针