leetcode 2576.求出最多标记下标
2576.求出最多标记下标
题意：
解析：
数组长为 n n n，因为一次标记两个，所以数组中最多有 ⌊ n 2 ⌋ \lfloor \frac{n}{2}\rfloor ⌊2n⌋ 对标记。
贪心的考虑，一个数 x 一定优先与满足 y ≥ 2 x y \ge 2x y≥2x 中最小的 y 进行匹配。
所以将数组排序，然后根据长度分成两部分，左侧较小的元素优先与右侧较小的元素进行匹配。用双指针扫描两部分数组，如果 n u m s [ j ] < 2 n u m [ i ] nums[j] < 2num[i] nums[j]<2num[i]，则不断将 j j 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 个数进行匹配。