interviewalgo
, ,
Source
Edit
History

414. 第三大的数

Introduction

Question：414. 第三大的数

Analysis

  1. 直接排序，然后从后面向前遍历求出第三大的数，时间复杂度O(nlogn)
  2. 遍历一次，手动用一些很复杂，很丑陋的条件语句来维护前三个最大值。

Implement

1
2
3
4
5
6
7
8
9
10
11
12
int thirdMax1(vector<int>& nums) {
    // 简单的 sort + 滑动 就能完成，但是这样时间复杂度为 `O(nlogn)`。
    // if (nums.size() == 1) return nums[0];
    sort(nums.begin(), nums.end());
    int rank = 0, i;
    for(i = nums.size() - 1;i > 0 && rank != 2;i--) {
        rank += (nums[i-1] < nums[i]);
    }
    if (rank == 2) return nums[i];
    else return *nums.rbegin();

}
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
inline bool check(vector<int> &nums, int i, int index) {
    return index < 0 || nums[i] > nums[index];
}
int thirdMax(vector<int>& nums) {
    int first = -1, second = -1, thrid = -1;
    for(int i = 0, size = nums.size();i < size;i++) {
        if (first >= 0 && second >= 0 && check(nums, i, thrid)) {
            // cout << first << " " << second << " " << thrid << endl;
            if (nums[i] > nums[first]) {
                thrid = second;
                second = first;
                first = i;
            } else if (nums[i] != nums[first] && nums[i] > nums[second]) {
                thrid = second;
                second = i;
            } else if (nums[i] != nums[first] && nums[i] != nums[second]) {
                thrid = i;
            }
        } else if (first >= 0 && check(nums, i, second)) {
            if (nums[i] > nums[first]) {
                second = first;
                first = i;
            } else if (nums[i] != nums[first]) 
                second = i;
        } else if (check(nums, i, first)) {
            first = i;
        }
    }
    if (thrid == -1) return nums[first];
    else return nums[thrid];
}

One More Thing