【LeetCode刷题集】--排序（三）

用户11915063

发布于 2025-11-20 09:19:43

450

题目一：第三大的数

题目链接：

414.第三大的数-力扣（LeetCode）

题意：

给你一个非空数组，返回此数组中第三大的数，若不存在，则返回数组中最大的数

思路：

先进行qsort排序，使数组变成一个降序数组，因为数组中的元素可能会重复，所以我们就要判断，数组重复的情况，我们可以定义个flag，i从1开始遍历，判断相邻两个数不相等就让flag++，当flag==2时，第三个大的数就出现了

代码实现：

int cmp(const void*a,const void*b)
{
    return *(int*)a<*(int*)b;//降序排列
}
int thirdMax(int* nums, int numsSize) 
{
    qsort(nums,numsSize,sizeof(int),cmp);
    int flag=0;
    for(int i=1;i<numsSize;i++)
    {
        //不同的数flag才++等到flag==2时说明数组里至少三个数不相同
        //此时flag==2刚好是第三个大的数
        if(nums[i]!=nums[i-1]&&++flag==2)
        {
            return nums[i];
        }
    }
    return nums[0];//没找到就返回最大的数
}

复杂度分析：

时间复杂度：O(Nlogn)

题目二：分发饼干

题目链接：

455.分发饼干-力扣（LeetCode）

题意：

一个孩子只能分到一块饼干，每个孩子都有一个胃口值，当你的饼干尺寸达到孩子的胃口值，孩子才满足，目标是尽可能让多的孩子满足

思路：

先利用qsort排序对s和g数组进行排序，定义一个计数器count来记录能满足孩子胃口的饼干个数，i作为s数组的下标，j作为g数组的下标，遍历s数组，i<sSize && j<gSize来保证两个数组不会越界，遍历中进行判断，如果饼干尺寸不满足第一个孩子的胃口（最小的胃口），就让数组s继续往后遍历，此时因为不满足if条件，j不会++，这样就能保证数组s一直找到满足孩子胃口的饼干为止，如果遍历结束还找不到，就返回count的值，因为没有一次满足，所以count还是为0的，如果饼干尺寸大于或者等于孩子胃口，那么就让count++，j++，继续找下一个孩子的胃口，此时i++找下一个饼干的尺寸，因为1个孩子对应1个饼干，s和g两个数组都继续向后走，再在s数组里找满足孩子胃口的饼干即可

代码实现：

int cmp(const void*a,const void*b)
{
    return *(int*)a-*(int*)b;
}
int findContentChildren(int* g, int gSize, int* s, int sSize) 
{
    qsort(g,gSize,sizeof(g[0]),cmp);
    qsort(s,sSize,sizeof(s[0]),cmp);    
    int count=0;
    int i=0,j=0;
    for(i=0;i<sSize&&j<gSize;i++)
    {
        if(s[i]>=g[j])
        {
            count++;
            j++;
        }
    }
    return count;
}

复杂度分析：

时间复杂度：O(Nlogn)

题目三：最长和谐子序列

题目链接：

594.最长和谐子序列-力扣（LeetCode）

题意：

子序列：数组中最大值-最小值=1的子数组，要求：不改变原数组的顺序返回最长的子序列

思路：

排序：我们只需要依次找到相邻两个连续相同元素的子序列，检查该这两个子序列的元素的之差是否为 1 双指针滑窗： begin 指向第一个连续相同元素的子序列的第一个元素，end 指向相邻的第二个连续相同元素的子序列的末尾元素，如果满足二者的元素之差为 1，则当前的和谐子序列的长度即为两个子序列的长度之和，等于end−begin+1。 循环：初始定义一个ret来计算长度，这里用到一个函数fmax（x,y）函数，来计算x和y的最大值，当循环结束返回的就是长度的最大值

代码实现：

int cmp(const void*a,const void*b)
{
    return *(int*)a-*(int*)b;
}
int findLHS(int* nums, int numsSize) 
{
    qsort(nums,numsSize,sizeof(nums[0]),cmp);
    int begin=0;
    int ret=0;
    for(int end=0;end<numsSize;end++)
    {
        while(nums[end]-nums[begin]>1)
        {
            begin++;
        }      
        if(nums[end]-nums[begin]==1)
        {
            ret=fmax(ret,end-begin+1);
        }
    }
    return ret;
}