【LeetCode】1796. 字符串中第二大的数字

题目描述

给你一个混合字符串 s ，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 -1 。
混合字符串 由小写英文字母和数字组成。

示例 1：

输入：s = “dfa12321afd”
输出：2
解释：出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。

示例 2：

输入：s = “abc1111”
输出：-1
解释：出现在 s 中的数字只包含 [1] 。没有第二大的数字。

提示：

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

方法一：我的解法

class Solution {
public:
    int secondHighest(string s) {
        vector<int> nums;
        int secondNum = -1;
        for(int i=0; i<s.size(); i++){
            if(s[i] >= '0' && s[i] <='9')
                nums.push_back(s[i]-'0');
        }
        sort(nums.begin(), nums.end(), greater<int>()); // 大的优先
        for(auto& num : nums){
            if(num!=nums[0]){
                secondNum = num;
                break;
            }    
        }
        return secondNum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法二：双指针遍历

class Solution {
public:
    int secondHighest(string s) {
        int firstNum = -1, secondNum = -1;
        for(auto& str : s){
            if(isdigit(str)){
                int cur = str - '0';
                if(cur > firstNum){
                    secondNum = firstNum;
                    firstNum = cur;
                }
                else if(cur < firstNum && cur > secondNum){
                    secondNum = cur;
                }
            }

        }

        return secondNum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

心得

• 这道题很简单，就是找到字符串中的第二大数字并返回，有以下两种情况返回 -1 ：第一种是字符串中不存在数字，第二种是字符串中只存在同一个数字。
• 第一种方法是我的思路，略显麻烦；
• 第二种方法是官方题解，复杂度更低一些。

• 方法一：我的解法
• 思路：
  • 首先，我先遍历整个字符串，将数字保存在 数组nums ；
  • 使用 sort 函数对 nums 进行降序排序；
    这里补充一下 sort 函数的知识，我经常忘记，sort（起始地址，结束地址，[比较器]），它默认是升序，如果想要实现降序，需要使用比较器 greater<数据类型>() ；
  • 最后遍历 nums ，找到第一个和 nums[0] 不同的元素，也就是数组的最大元素。
• 时间复杂度： O（n logn），等同于 sort 的时间复杂度；
• 空间复杂度： O（n）
  

方法二：官方题解

• 思路
  我的方法是将数字保存在一个数组里，其实完全可以省略这个步骤，在遍历的时候，用两个指针，一个指向 firstNum ，一个指向 secondNum，每次遍历到一个新数字，就判断是否要更新两个指针，最后返回 secondNum 即可。
• 此外，这个解法我需要学习的有：
  • 函数 isdigit()，可以直接判断该字符是否是数组。
• 时间复杂度： O（n）
• 空间复杂度： O（1）