C++ LeetCode1796字符串中第二大數(shù)字
LeetCode 1796.字符串中第二大的數(shù)字
力扣題目鏈接:leetcode.cn/problems/se…
給你一個(gè)混合字符串 s
,請(qǐng)你返回 s
中 第二大 的數(shù)字,如果不存在第二大的數(shù)字,請(qǐng)你返回 -1
。
混合字符串 由小寫英文字母和數(shù)字組成。
示例 1:
輸入:s = "dfa12321afd"
輸出:2
解釋:出現(xiàn)在 s 中的數(shù)字包括 [1, 2, 3] 。第二大的數(shù)字是 2 。
示例 2:
輸入:s = "abc1111"
輸出:-1
解釋:出現(xiàn)在 s 中的數(shù)字只包含 [1] 。沒有第二大的數(shù)字。
提示:
1 <= s.length <= 500
s
只包含小寫英文字母和(或)數(shù)字。
方法一:遍歷
題目分析
題目中說的“第二大”數(shù)字,到底什么是第二大?英文原文是“Second largest”
也就是說,是從大到小第二個(gè)數(shù),不是從小到大第二個(gè)數(shù)。
樣例中“123”,不論是從小到大還是從大到小都是“2”,不如把樣例換成“1234”,這樣答案是“3”,就一目了然了。
解題思路
首先開辟一個(gè)大小為“10”的布爾數(shù)組,初始值為false
接著遍歷字符串,如果字符串的某個(gè)字符是數(shù)字,那么就將對(duì)應(yīng)的那個(gè)布爾值標(biāo)記為true
接著,用一個(gè)變量foundFirst
來記錄是否已經(jīng)找到了最大值,初始值為false
從9
到0
遍歷布爾數(shù)組,如果遇到某個(gè)值為true
,就看foundFirst
是否已經(jīng)為true
- 如果為
true
,就返回當(dāng)前的對(duì)應(yīng)元素 - 否則,將
foundFirst
標(biāo)記為true
若遍歷結(jié)束后仍未找到“第二大數(shù)”,那么就返回-1
復(fù)雜度分析
- 時(shí)間復(fù)雜度O(len(s))
- 空間復(fù)雜度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字符串中第二大數(shù)字的詳細(xì)內(nèi)容,更多關(guān)于C++ 字符串第二大數(shù)字示例的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C++中的std::initializer_list使用解讀
這篇文章主要介紹了C++中的std::initializer_list使用,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-07-07Qt掃盲篇之QRegularExpression正則匹配總結(jié)
QRegularExpression是Qt5.0引進(jìn)的,修復(fù)了很多bug,提高了效率,使用時(shí)建議使用QRegularExpression,下面這篇文章主要給大家介紹了關(guān)于Qt掃盲篇之QRegularExpression正則匹配的相關(guān)資料,需要的朋友可以參考下2023-03-03C++內(nèi)存對(duì)齊的實(shí)現(xiàn)
本文主要介紹了C++內(nèi)存對(duì)齊的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02Linux下g++編譯與使用靜態(tài)庫和動(dòng)態(tài)庫的方法
下面小編就為大家?guī)硪黄狶inux下g++編譯與使用靜態(tài)庫和動(dòng)態(tài)庫的方法。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-05-05