C++怎么解決字符串中第二大數字問題

本篇內容主要講解“C++怎么解決字符串中第二大數字問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C++怎么解決字符串中第二大數字問題”吧!

字符串中第二大的數字

給你一個混合字符串 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++怎么解決字符串中第二大數字問題”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！