一、题目描述
给你一个混合字符串 s
,请你返回 s
中 第二大 的数字,如果不存在第二大的数字,请你返回 -1
。
混合字符串 由小写英文字母和数字组成。
示例 1:
输入:s = "dfa12321afd"
输出:2
解释:出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。
示例 2:
输入:s = "abc1111"
输出:-1
解释:出现在 s 中的数字只包含 [1] 。没有第二大的数字。
提示:
1 <= s.length <= 500
s
只包含小写英文字母和(或)数字。
来源:力扣(LeetCode) 链接:leetcode.cn/problems/se…
二、解题思路
第一遍读题的时候,想到的遍历一遍是把数字放到小顶堆里面进行排序……两个数好像不值得~
字符串包含英文字母和数字,首先要做的就是把英文字母筛选掉,单个字符可以转成ASCII码比较大小进行筛选。
字符串中共涉及到0-9这几个数字,数字范围是固定的,这时候可以使用桶排序的思想,创建一个数组,数组下标就是字符串中的数字,数组的值可以表示是否在字符串中遇到了这个数字。遇到数字的时候,把对应数组位置的值修改一下即可。
因为数组下标是有序的,最后把这个数组倒序遍历一遍,遇到第二个修改值的位置,把下标输出即可。
既然思路确定了,那么就开始写代码了
class Solution {
public int secondHighest(String s) {
// 从题目可以看到,涉及的数字只有0-9,所以可以使用一个数组存放结果,如果字符串中出现了这个数字,就在数组中标为1
// 最后的时候,从大往小,遍历结果数组,遇到第二个存放1的位置,直接返回坐标即可
int[] result = new int[10];
char[] chars = s.toCharArray();
for (char c : chars) {
// 遍历字符串,过滤掉字母,数字直接作为数组下标
if (c >= '0' && c <= '9') {
result[c - '0'] = 1;
}
}
// 需要一个标记,来区分是第一大还是第二大的数字
boolean flag = false;
// 遍历记录结果的数字
for (int i = 9; i >= 0; i--) {
// 如果存放的数字为1,说明字符串中有这个数字
if (result[i] == 1) {
// 如果标记为true,表示这是第二次遇到字符串中出现的数字,直接返回
if (flag) {
return i;
} else {
//第一次遇到字符串中出现的数字,此时是最大的数字
flag = true;
}
}
}
return -1;
}
}
- 时间复杂度:
O(n)
,其中 n 表示字符串的长度,我们遍历一遍字符串和结果数组,结果数组的长度在时间复杂度中忽略。 - 空间复杂度:
O(1)
。存放结果的数组长度是固定的。
这地方使用int数组占用的空间还是比较多的,使用boolean类型的会更好一些。但是转念一想,这里只涉及到两个数字的变化:最大数和第二大数,那么我们是不是可以使用两个变量记录数字呢?
那么就遍历字符串遇到数字的时候就涉及到四种情况:
- 遇到的数字比最大数还要大,此时就要更新最大数和第二大数
- 遇到的数字跟最大数相等,此时最大数和第二大数都不需要更新
- 遇到的数字比最大数小,比第二大数大,此时只要更新第二大数
- 遇到的数字小于等于第二大数,此时最大数和第二大数都不需要更新
代码示例
class Solution {
public int secondHighest(String s) {
// max记录最大的数字,min记录第二大的数字
int max = -1;
int min = -1;
char[] chars = s.toCharArray();
for (char c : chars) {
// 遍历字符串字符,如果是字母,直接跳过
// 如果当前遇到的数字和最大的数字相等,直接跳过
if (c > '9' || c - '0' == max) {
continue;
}
// 字符串相减得到实际数字的值
int temp = c - '0';
// 如果当前遇到的数字比最大数还要大,则更新最大数和第二大数的值
if (temp > max) {
min = max;
max = temp;
} else if (temp > min) {
// 如果当前遇到的数字比最大数小,比第二大数大,更新第二大数的值
min = temp;
}
}
return min;
}
}
- 时间复杂度:
O(n)
,其中 n 表示字符串的长度,我们只需遍历一遍字符串。 - 空间复杂度:
O(1)
。使用到的变量数量进一步减少