【每日一题】LeetCode 2576.求出最多标记下标（贪心、数组、双指针、二分查找、排序）
题目描述
给定一个整数数组 nums，数组下标从 0 开始。你需要执行以下操作，直到无法再执行为止：
- 选择两个互不相同且未标记的下标
i和j。 - 满足条件
2 * nums[i] <= nums[j]，则标记下标i和j。
你需要返回 nums 中最多可以标记的下标数目。
思路分析
这个问题可以通过贪心算法来解决。我们首先对数组进行排序，这样可以保证较小的元素在前面，较大的元素在后面。然后，我们从数组的两端开始，每次选择一个较小的元素 i 和一个较大的元素 j，检查是否满足 2 * nums[i] <= nums[j] 的条件。如果满足，我们就标记这两个下标，并将 i 和 j 都向后移动一位，继续检查下一个较小的元素和下一个较大的元素。这个过程会一直进行，直到 i 达到数组的中点或者 j 达到数组的末尾。
输入示例
示例 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 。
代码实现
import java.util.Arrays;
class Solution {
public int maxNumOfMarkedIndices(int[] nums) {
// 对数组进行排序
Arrays.sort(nums);
int n = nums.length;
// 初始化标记计数器
int count = 0;
// 初始化两个指针，i 从数组开始，j 从中点开始
int i = 0, j = n / 2;
// 遍历数组直到 i 到达中点或者 j 到达数组末尾
while (i < n / 2 && j < n) {
// 移动 j 直到找到满足条件的 j
while (j < n && 2 * nums[i] > nums[j]) {
j++;
}
// 如果找到了满足条件的 j，标记 i 和 j
if (j < n) {
count += 2;
i++;
j++;
}
}
// 返回标记的下标数目
return count;
}
}