给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例 1:
输入 : [3, 2, 1]
输出 : 1
解释 : 第三大的数是 1.
示例 2 :
输入 : [1, 2]
输出 : 2
解释 : 第三大的数不存在, 所以返回最大的数 2 .
示例 3 :
输入 : [2, 2, 3, 1]
输出 : 1
解释 : 注意,要求返回第三大的数,是指第三大且唯一出现的数。
存在两个值为2的数,它们都排第二。
思想方法:遍历找值,找到自己所需要的值保存起来,判断输出。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int thirdMax(int* nums, int numsSize) { long first = LONG_MIN; long second = LONG_MIN; long third = LONG_MIN; int i = 0; for (i = 0; i < numsSize; i++) { if (nums[i] > first) { first = nums[i]; // 将数组里的最大值赋值给first } } for (i = 0; i < numsSize; i++) { if (nums[i] > second && nums[i] != first) { second = nums[i]; //将第二大的值付给second } } for (i = 0; i < numsSize; i++) { if (nums[i] > third && nums[i] != first && nums[i] != second) { third = nums[i]; //第三的值赋值给third } } if (third != LONG_MIN) //判断是否至少有三个不同的数 { return third; } return first; } int main() { int num[] = { 2, 2, 3, 1 }; int len = sizeof(num) / sizeof(int); int a = thirdMax(num, len); printf("%dn", a); system("pause"); return 0; }
给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如(a1, b1), (a2, b2), ..., (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。
示例 1:
输入 : [1, 4, 3, 2]
输出 : 4
解释 : n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int arrayPairSum(int* nums, int numsSize) { int sum = 0; for (int i = 0; i < numsSize - 1; i++){ for (int j = 0; j < numsSize - i - 1; j++){ if (nums[j] > nums[j + 1]){ int t = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = t; } } } for (int k = 0; k < numsSize; k += 2){ sum += nums[k]; } return sum; } int main() { int num[] = { 4, 2, 3, 1 }; int len = sizeof(num) / sizeof(int); int a = arrayPairSum(num, len); printf("%dn", a); system("pause"); return 0; }
最后
以上就是失眠飞机最近收集整理的关于给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。的全部内容,更多相关给定一个非空数组,返回此数组中第三大内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复