题干描述
给你一个下标从 0 开始的整数数组 nums 。
一开始，所有下标都没有被标记。你可以执行以下操作任意次：
- 选择两个 互不相同且未标记 的下标
i和j，满足2 * nums[i] <= nums[j]，标记下标i和j。
请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。
示例 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 。
题干分析
题目理解
题目给定一个整数数组nums，要求找出数组中最多可以标记的下标数目。操作条件是每次可以选择两个未标记的下标i和j，满足2 * nums[i] <= nums[j],然后标记着两个下标。目标是执行尽可能多的标记操作。
该题目的本质是要求我们找出符合条件的最多配对数，且配对的条件是2 * nums[i] <= nums[j]，即选择较小的nums[i]和较大的nums[j]进行配对。
解题思路
1.排序数组
- 为了便于处理每一对下标i和j，我们可以将数组nums按照肾虚排序。排序后的数组让我们能够更加轻松地选择较小的值nums[i]和较大的值nums[i]，并比较是否满足条2 * nums[i] <= nums[j]。
- 排序的时间复杂度为O（n log n）。
2.双指针法
排序后，可以使用双指针来处理配对问题。一个指针i从数组的前半部分开始，表示较小值的位置；另一个指针j从数组的后半部分开始，表示较大值的位置。
初始化指针
- 指针i：从0开始，遍历前一半较小的元素
- 指针j：从数组中间numsSize / 2喀什，遍历后一半较大的元素。
配对指针
- 如果满足条件2 * nums[i] <= nums[j]，我们可以标记着两个小标，然后移动两个指针，i指向下一个较小值，j指向下一个较大值。
- 如果不满足条件，则移动j指向下一个更大的值，直到找到可以与i配对的值。
3.计数
- 每次找到一个符合条件的配对时，我们将计数器count增加2，表示标记了两个下标。
- 最后返回count即为最多可以标记的下标数目。
详细步骤
1.排序数组
- 将数组nums进行升序排序，这样尅可以更容易找到较小值nums[i]和较大值nums[j].
- 例如，输入nums = [9, 2, 5, 4],排序后的数组为[2,4,5,9]。
2.初始化双指针
- i：指向数组较小的部分，初始值为0。
- j：指向数组较大的部分，初始值为numsSize / 2（数组中间的位置）。
- 例如对于数组[2,4,5,9],i从0开始，j从2开始。
3.使用双指针遍历数组并配对
- 判断2 * nums[i] <= nums[j]是否成立。
- 如果成立，则标记这两个下标，移动i和j。
- 如果不成立，则只移动j，继续寻找更大的值。
4.计数并返回
- 每找到一对符合条件的下标，计数器增加2，最后返回计数器的值。
#include <stdio.h>
#include <stdlib.h>//比较函数，用于qsort排序
int cmp(const void* a, const void* b){return (*(int*)a - *(int*)b);
}//计算最多可以标记的下标数组
int maxNumOfMarkedIndices(int* nums, int numsSize){//对数组进行升序排序qsort(nums, numsSize, sizeof(int), cmp);int i = 0;//指向较小值的指针int j = numsSize / 2;//指向较小值的指针int count = 0;//计数以标记的下标数目//使用双指针遍历数组while(i < numsSize / 2 && j < numsSize){if(2 * nums[i] <= nums[j]){//找到符合条件的配对，计数增加count += 2;i++;//移动小值指针j++;//移动大值指针}else{//如果条件不满足，移动大值指针j++;}}return count;
}