C++ LeetCode1796字符串中第二大數字

更新時間：2022年12月16日 15:34:49 作者：LetMeFly

這篇文章主要為大家介紹了C++ LeetCode1796字符串中第二大數字示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

LeetCode 1796.字符串中第二大的數字

力扣題目鏈接：leetcode.cn/problems/se…

給你一個混合字符串 s ，請你返回 s 中 第二大 的數字，如果不存在第二大的數字，請你返回 -1 。

混合字符串 由小寫英文字母和數字組成。

示例 1：

輸入：s = "dfa12321afd"
輸出：2
解釋：出現在 s 中的數字包括 [1, 2, 3] 。第二大的數字是 2 。

示例 2：

輸入：s = "abc1111"
輸出：-1
解釋：出現在 s 中的數字只包含 [1] 。沒有第二大的數字。

提示：

1 <= s.length <= 500
s 只包含小寫英文字母和（或）數字。

方法一：遍歷

題目分析

題目中說的“第二大”數字，到底什么是第二大？英文原文是“Second largest”

也就是說，是從大到小第二個數，不是從小到大第二個數。

樣例中“123”，不論是從小到大還是從大到小都是“2”，不如把樣例換成“1234”，這樣答案是“3”，就一目了然了。

解題思路

首先開辟一個大小為“10”的布爾數組，初始值為false

接著遍歷字符串，如果字符串的某個字符是數字，那么就將對應的那個布爾值標記為true

接著，用一個變量foundFirst來記錄是否已經找到了最大值，初始值為false

從9到0遍歷布爾數組，如果遇到某個值為true，就看foundFirst是否已經為true

如果為true，就返回當前的對應元素
否則，將foundFirst標記為true

若遍歷結束后仍未找到“第二大數”，那么就返回-1

復雜度分析

時間復雜度O(len(s))
空間復雜度O(C)，這里C=10，也可以理解為O(1)

AC代碼

C++

class Solution {
public:
    int secondHighest(string& s) {
        bool bin[10] = {false};
        for (char c : s) {
            if (c >= '0' && c <= '9')
                bin[c - '0'] = true;
        }
        bool foundFirst = false;
        for (int i = 9; i >= 0; i--) {
            if (bin[i]) {
                if (foundFirst) {
                    return i;
                }
                else {
                    foundFirst = true;
                }
            }
        }
        return -1;
    }
};

以上就是C++ LeetCode1796字符串中第二大數字的詳細內容，更多關于C++ 字符串第二大數字示例的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: