最新华为OD机试真题-字符串筛选排序(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 字符串筛选排序(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

字符串筛选排序

问题描述

LYA 有一个由 个大小写字母组成的字符串 。她想按照字母的 码值从小到大对字符串进行排序，并找到排序后的字符串中第 个最小 码值的字母在原字符串 中的位置索引（字符串的第一个字母位置索引为 ）。

如果 大于字符串 的长度，则输出原字符串中 码值最大的字母所在的位置索引。

如果第 个最小 码值的字母在原字符串中出现多次，则输出该字母第一次出现的位置索引。

输入格式

第一行输入一个由大小写字母组成的字符串 。

第二行输入一个正整数 ，表示要查找的第 小 码值的字母。

输出格式

输出一个整数，表示第 个最小 码值的字母在原字符串 中第一次出现的位置索引。

如果 大于字符串 的长度，则输出原字符串中 码值最大的字母所在的位置索引。

样例输入1

AbCdeFG
3

样例输出1

5

样例输入2

fAdDAkBbBq
4

样例输出2

6

数据范围

题解

本题需要先对字符串按照 码值从小到大进行排序，然后找到排序后的第 个字母在原字符串中第一次出现的位置索引。

首先，我们可以直接使用语言内置的排序函数对字符串进行排序，得到按 码值从小到大排序后的字符串。

然后，我们取排序后字符串的第 个字母（如果 大于字符串长度，则取最后一个字母），记为 。

接下来，我们遍历原字符串，找到字母 第一次出现的位置索引即可。

时间复杂度为 ，其中排序的时间复杂度为 ，遍历查找的时间复杂度为 。

参考代码

• Python

s = input()
k = int(input())
sorted_s = sorted(s)
ch = sorted_s[min(k - 1, len(s) - 1)]
print(s.index(ch))

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int k = sc.nextInt();
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        char ch = chars[Math.min(k - 1, s.length() - 1)];
        System.out.println(s.indexOf(ch));
    }
}

• Cpp

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int k;
    cin >> k;
    string sorted_s = s;
    sort(sorted_s.begin(), sorted_s.end());
    char ch = sorted_s[min(k - 1, (int)s.length() - 1)];
    cout << s.find(ch) << endl;
    return 0;
}