👀个人简介：一个正在努力奋斗逆天改命的二本觉悟生
📖个人专栏：《C语言》《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)
题目二：分发饼干
题目链接：
题意：
一个孩子只能分到一块饼干，每个孩子都有一个胃口值，当你的饼干尺寸达到孩子的胃口值，孩子才满足，目标是尽可能让多的孩子满足
思路：
先利用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)
题目三：最长和谐子序列
题目链接：
题意：
子序列：数组中最大值-最小值=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;
}复杂度分析：
时间复杂度：O(Nlogn)
往期回顾：
【LeetCode刷题集】--排序（一）
【LeetCode刷题集】--排序（二）
总结：这篇博客给大家讲解了三个排序算法题，其中涉及了fmax()函数，每天积累一个小知识点，就可以逐渐解决一些难题，算法能力不是一蹴而就，而是通过一朝一夕的坚持刷题而积累的！如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持🌹🌹🌹