2576.求出最多标记的下标

Problem: 2576. 求出最多标记下标>
思考贪心方向错误，记录对于灵茶山艾府解答的理解。

解题方法

首先还是思考题目中可能存在的隐藏性质，来把题目转为可计算机求解的另一种表达方式。可以发现，如果数组有k个匹配对，那么前k个元素和最后k个元素一定能一一匹配上。这一点其实用反证法很好想，i从0开始自增到k，如果第i个元素的两倍小于第n-k+i个元素，那么就只能往第n-k+1个以后去找，但是这样就没有k个配对了。

接下来就是如何利用这个性质。

我们可以利用k个匹配对这个关键点，尝试不同的最大匹配数k。为了尽可能少的遍历k值，自然想到二分答案的做法。显然k越大的情况下，可以匹配的对数越多，符合二分搜索的条件。二分搜索k，然后验证前述性质，如果满足就尝试取更大的k值，反之同理即可。

思路

起初想到的思路是首先将数组进行排序，然后使用贪心，每次将最大的和最接近其二分之一的数进行匹配，但是这样的做法可以举出反例3,4,6,8,100,101，是不正确的。

对于这一类题目，在一个性质不行的时候，要试着把答案也作为一个变量，来思考其他的性质，这样可以利用二分法，是非常高效的。

复杂度

• 时间复杂度: $O(nlogn)$，二分答案$O(logn)$复杂度，n为数组元素。
• 空间复杂度: $O(1)$，若干常量空间。

Code

class Solution {
    public int maxNumOfMarkedIndices(int[] nums) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length / 2; // 开区间
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(nums, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right * 2; // 最多匹配 left 对，有 left * 2 个数
    }
    
    private boolean check(int[] nums, int k) {
        for (int i = 0; i < k; i++) {
            if (nums[i] * 2 > nums[nums.length - k + i]) {
                return false;
            }
        }
        return true;
    }
}