当前位置：首页 > article >正文

LeetCode 每日一题求出最多标记下标

article 2024/9/19 9:53:50

求出最多标记下标

题目如下↓

给你一个下标从 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 。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 109

解题思路

题目的意思就是在数组里面找一对数，这一对数中大的数大于等于小的数的两倍，我们需要返回最多可以有多少对数

那么既然是一个小的数与大的数进行配对，那么我们不如先用 qsort() 对数组进行排序

然后我们接着对题目进行分析，有一个想法是先找到最小的数，然后再找到最小的可以与之配对的数，但是这样做可以找到最多的对数吗？例如数组 [2,4,5,9] 如果按照上述想法，那么就只有一对（2，4），但是实际上可以有（2，5）（4，9）两对，所以上述想法存在问题

我们换一个思路，对于一个数组，最好的情况就是所有的数都可以配对或者只留下一个数，那么我们不如将排好序的数组平分为两个区域，左边的区域与右边的区域进行配对，也就是从左区域的最小数开始寻找右区域的可以配对的数，利用双指针进行枚举，即可找到最多的对数。

那么为什么我们的第一个想法不对呢？

因为我们直接去找可以配对的最小数字，有可能是左边区域的两个数进行了配对，然而因为右边区域的所有数字都比左边大，所以左边配对的较小的数一定可以在右边找到数配对，另一个较大的数也有可能与右边区域进行配对，这样就导致少了一个可能配对的机会，导致对数不一定是最大。另外，由于左边与右边的数字的数量最多只差1，所以左边的数只与右边的数进行配对并不会导致最多配对数的变小。

下面上代码！

int maxNumOfMarkedIndices(int* nums, int numsSize){
    int s=0;
    int compare(int*a,int*b)
    {
        return *a - *b;
    }
    qsort(nums,numsSize,sizeof(int),compare);
    int m = numsSize/2;
    int l=0,r=m;
    while(l<m && r<numsSize)
    {
        if(nums[r]>=nums[l]*2)
        {
            s+=2;
            l++;
            r++;
        }
        else
        {
            r++;
        }
    }
    return s;
}