[LeetCode] Third Maximum Number

red_bricks 发布于2019-08-19 10:58 / 1579人阅读

Problem

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.
Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

Solution

class Solution {
    public int thirdMax(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int first = Integer.MIN_VALUE, second = first, third = first;
        boolean firstExists = false, secondExists = false, thirdExists = false;
        for (int num: nums) {
            if (num >= first) {
                if (!firstExists) {
                    first = num;
                    firstExists = true;
                } else if (num == first) {
                    continue;
                } else {
                    if (secondExists) {
                        third = second;
                        thirdExists = true;
                    } else {
                        secondExists = true;
                    }
                    second = first;
                    first = num;
                }
            } else if (num >= second) {
                if (!secondExists) {
                    second = num;
                    secondExists = true;
                } else if (num == second) {
                    continue;
                } else {                    
                    if (!thirdExists) {
                        thirdExists = true;
                    }                   
                    third = second;
                    second = num;
                }
            } else if (num >= third) {
                thirdExists = true;
                third = num;
            }
        }
        System.out.println(first);
        System.out.println(second);
        System.out.println(third);

        return thirdExists == false ? first : third;
    }
}

云服务器服务器托管 Third Maximum LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76771.html

leetcode 414 Third Maximum Number

摘要：题目详情给定一个输入的数组，我们需要找出这个数组中第三大的数，而且时间复杂度必须是如果不存在第三大的数，则返回最大的数。思路因为时间复杂度为，所以预排序是不可以的我们一定要在一次遍历结束后就找到这个第三大的值。题目详情 Given a non-empty array of integers, return the third maximum number in this array....

anquan 2019-08-15 13:54 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
LeetCode[321] Create Maximum Number

摘要：算法复杂度思路贪心算法，先能组成的数的组合，然后针对每一个组合，考虑每一个数组能够组成的最大的位或者位数。对不同组合生成的最大数进行比较，得到所能得到的最大的值。代码的方法去找这个数。 LeetCode[321] Create Maximum Number Given two arrays of length m and n with digits 0-9 representing ...

UsherChen 2019-08-14 16:38 评论0 收藏0