leetcode 2576.求出最多标记下标

2576.求出最多标记下标

题意：

解析：

数组长为 $n$，因为一次标记两个，所以数组中最多有 $\lfloor \frac{n}{2}\rfloor$ 对标记。

贪心的考虑，一个数 x 一定优先与满足 $y\ge 2x$ 中最小的 y 进行匹配。

所以将数组排序，然后根据长度分成两部分，左侧较小的元素优先与右侧较小的元素进行匹配。用双指针扫描两部分数组，如果 $nums[j]<2num[i]$，则不断将 $j$ 指针后移。

代码：

int maxNumOfMarkedIndices(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());int pos = n/2;int ans = 0;for(int i = 0, j = pos; i < pos && j < n; i++, j++){while(j < n && nums[i]*2 > nums[j])j++;if(j < n)ans += 2;}return ans;}

二分答案：

另一种思路是二分答案。二分匹配的对数 k，如果能有 k 对匹配，则一定是最小的 k 个数与最大的 k 个数进行匹配。