414.第三大的数

发表于 | 分类于
字数统计: 426 | 阅读时长 ≈ 1

一、题目描述

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1:

1
2
3
4
5
输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.

示例 2:

1
2
3
4
5
输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .

示例 3:

1
2
3
4
5
6
输入: [2, 2, 3, 1]

输出: 1

解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。

二、题解

1.算法描述

  • 窗口滑动

2.个人分析

  • 初始化一个长度为三的滑动窗口，用三个变量实现。遍历数组时，使用数组中的元素更新窗口中的值，使用flag标记窗口中元素的更新次数，如果flag>=3，则说明窗口中的元素被全部更新，即返回窗口中的最小值；否则，falg只更新了1次或2次，即第三大的数不存在, 所以返回最大的数。

3.代码

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
int thirdMax(int *nums, int numsSize)
{
    if (numsSize == 1)
        return nums[0];
    if (numsSize == 2)
        return nums[0] >= nums[1] ? nums[0] : nums[1];
    int i, flag = 0, intmin = 1;//intmin是为了排除掉数组中的INT_MIN
    int min = -__INT_MAX__ - 1;
    int mid = -__INT_MAX__ - 1;
    int max = -__INT_MAX__ - 1;
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] == -__INT_MAX__ - 1 && intmin)
        {
            flag++;
            intmin = 0;
        }
        if (nums[i] > max)
        {
            flag++;
            min = mid;
            mid = max;
            max = nums[i];
        }
        else if (nums[i] > mid && nums[i] < max)
        {
            flag++;
            min = mid;
            mid = nums[i];
        }
        else if (nums[i] > min && nums[i] < mid)
        {
            flag++;
            min = nums[i];
        }
    }
    return flag >= 3 ? min : max;
}