力扣-414.第三大的数（两种解法）

文章目录

- 第三大的数
- - 解法一（排序加遍历对比）
  - 解法二（遍历一遍加迭代）

第三大的数

题目：

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

示例 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;//判断第三个值是否是原值
}