文章目录
- 第三大的数
- 解法一（排序加遍历对比）
- 解法二（遍历一遍加迭代）
第三大的数
题目：
给你一个非空数组，返回此数组中第三大的数 。如果不存在，则返回数组中最大的数。
示例 1： 输入：[3, 2, 1] 输出：1
解释：第三大的数是 1 。示例 2： 输入：[1, 2] 输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。示例 3： 输入：[2, 2, 3, 1] 输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。 此例中存在两个值为
2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
解法一（排序加遍历对比）
分析：
1.因为是要第三大的数，我们可以先判断数组的长度，如果为 1 则直接放回数组的第一个数，为2就判断哪个大在返回最大值。
2.当我们判断数组长度大于等于3后可以将它们进行降序排序，然后再用循环判断是否有三个数不相等（因为有可能整个数组都是同一个数或者是由两个数组成），然后再输出第三大的元素
在写代码之前我们先来简单介绍一个排序的库函数 qsort
对所指向的数组元素进行排序，每个元素的长度为字节，使用函数确定顺序。
此函数使用的排序算法通过调用指定的函数来比较元素对，并将指向元素的指针作为参数。
该函数不返回任何值，而是通过对数组的元素进行重新排序来修改所指向的数组的内容.
注意的是 compar函数的创建的格式和 qsort的一样： int (*compar)(const void*,const void*));//这个是自己创建的
qsort的使用
void qsort (void* base, size_t num, size_t size,
int (*compar)(const void*,const void*));
我们来实现一个整形排序
int hanshu(const void* p1,const void* p2) {//这里要按照qsort中的函数参数类型来写
//int (*compar)(const void*,const void*));
return (*((int*)p1) - *((int*)p2));//返回-上面有解释 (int*)p1--强制转换为int类型指针
}
int main() {
int arr[] = { 5,3,2,4,1 };
int zs = sizeof(arr) / sizeof(arr[0]);//数组大小
qsort(arr, zs, sizeof(arr[0]), hanshu);//按照规则填入， sizeof(arr[0])一个元素占多少字节
for (int i = 0; i < zs; i++)//打印
printf("%d ", arr[i]);
return 0;
}
我们来看看运行结果：
成功完成排序
好，我们接下来就通过代码实现：
int te(const void* p1, const void* p2) {//排序判断大小的函数
return *(( int*)p2) >*(( int*)p1);//返回 > 就交换
}
int thirdMax(int* nums, int numsSize) {
if (numsSize == 1) {//判断长度
return nums[0];
}
else if (numsSize == 2) {//判断长度，只有2个元素，判断大小再返回
int max = nums[0];
if (max < nums[1])
max = nums[1];
return max;
}
else {
qsort(nums, numsSize, sizeof(int), te);//实现排序，一定要按照函数的格式放值
int r = 0,t;//r是用来判断是否有三个不同的数，t是保留第三大数的下标的
for (int j = 0; j < numsSize-1; j++) {
if (nums[j] != nums[j + 1]) {//前后不一样r++
r++;
if (r == 2) {//当r==2时证明有三个不同的元素了，此时可以结束判断了
t = j+1;//记录下标
break;
}
}
}
if (r != 2)//判断是否够三个数，不够直接返回最大值
return nums[0];
else//r==2返回第三大的元素
return nums[t];
}
}
以上就是第一种解法的详细代码和注释了
解法二（遍历一遍加迭代）
分析：
1.我们只要求前三大的元素，那么我们可以设置三个变量分别代表最大，第二，第三大的元素。
2.再对所有元素判断，判断在我们设置的三个变量的哪个区间里，再进行迭代
3.最后再判断第三大的变量是否被改变，要是被改变了就是返回改值，不然返回最大值
我们先介绍一下
int、long、longlong等的最大值和最小值的宏定义（部分）
头文件：<limits.h>
#define SHRT MIN (-32768)//short-min
#define SHRT_MAX 32767 //short-max
#define USHRT_MAX 0xffff //无符号 short-max
#define INT MIN (-2147483647-1)//int-min
#define INT_MAX 2147483647 //int-max
#define UINT_MAX 0xffffffff //无符号 int-max
#define LONG MIN (-2147483647L -1)//long-min
#define LONG MAX 2147483647L //long-max
#define ULONG_MAX 0xffffffffUL// 无符号long-man
#define LLONG MAX 9223372036854775807i64 //long long-man
#define LLONG MIN (-9223372036854775807i64 -1)//long long-min
#define ULLONG MAX 0xffffffffffffffffui64//无符号 longlong-max
代码：
int thirdMax(int* nums, int numsSize) {
long a = LONG_MIN;//最大元素---这里用long是因为力扣那个案例里有大于int类型的值，LONG_MIN--long的最小值
long b= LONG_MIN;//第二个大元素
long c = LONG_MIN;//第三大元素
for (int i = 0; i < numsSize; i++) {
if (nums[i] > a) {//比最大值都大，将数值由大往小交换
c = b;
b = a;
a = nums[i];
}
else if (nums[i]<a && nums[i]>b) {//在最大值和第二大的中间，这时不动最大值，其他往下交换
c = b;
b = nums[i];
}
else if (nums[i]<b && nums[i]>c) {//在第二值和第三大的中间，这时不动最大值和第二大，将第三换掉
c = nums[i];
}
}
return c == LONG_MIN ? a : c;//判断第三个值是否是原值
}
以上就是第二种解法的详细代码和注释了
今天的分享就到这，谢谢大家观看！
文章出处登录后可见！
