LeetCode 2576. 求出最多标记下标(二分+双指针)
原题链接
中等
作者:
我是java同学
,
2023-09-16 16:31:12
,
所有人可见
,
阅读 74
class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int i = 0;
for (int j = (n + 1) / 2; j < n; j ++ )
if (nums[i] * 2 <= nums[j])
i ++ ;
return i * 2;
}
};
class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int l = 0, r = n / 2;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid, n, nums)) l = mid;
else r = mid - 1;
}
return r * 2;
}
bool check(int mid, int n, vector<int>& nums) {
for (int i = 0; i < mid; i ++ )
if (nums[i] * 2 > nums[n - mid + i])
return false;
return true;
}
};