leetcode

leetcode 414题

Posted by franki on October 12, 2022

leetcode 414 第三大的数

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

示例1

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例2

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例3

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

思路

最简单的方式就是通过排序的情况，然后去排序第三的位置，当然还得判断第三个元素是否是重复的，重复得顺延，知道不是相等的未知，得注意一些边界条件；但是这样的复杂度显然是高于 O(N)，所以想要在 O(N) 的情况下完成，需要用三个变量来记录这个大小的变化，复杂度可以降到 O(N)，可以不断的遍历当前数组的元素，不断判断，不断更新三个变量值，直到遍历结束，即可得出结果

代码

var thirdMax = function(nums) {
    let a = Number.MIN_SAFE_INTEGER, b = Number.MIN_SAFE_INTEGER, c = Math.MIN_SAFE_INTEGER;

    for (const v of nums) {
        if (v > a) {
            c = b;
            b = a;
            a = v;
        } else if (v > b && v < a) {
            c = b;
            b = v;
        } else if (v > c && v < b) {
            c = v;
        }
    }

    if (c === Number.MIN_SAFE_INTEGER) {
        return a;
    }

    return c;
};

复杂度分析:

  • 时间复杂度: O(N)
  • 空间复杂度：O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS