【2024年华为OD机试】(C卷,100分)- 字符串筛选排序 （Java JS PythonC/C++）

一、问题描述

题目描述

输入一个由N个大小写字母组成的字符串

按照ASCII码值从小到大进行排序

查找字符串中第K个最小ASCII码值的字母 (k >= 1)

输出该字母所在字符串中的位置索引 (字符串的第一个位置索引为0)

k如果大于字符串长度则输出最大ASCII码值的字母所在字符串的位置索引

如果有重复字母则输出字母的最小位置索引

输入描述

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

第二行输入k，k必须大于0，k可以大于输入字符串的长度

输出描述

输出字符串中第K个最小ASCII码值的字母所在字符串的位置索引

k如果大于字符串长度则输出最大ASCII码值的字母所在字符串的位置索引

如果第K个最小ASCII码值的字母存在重复，则输出该字母的最小位置索引

用例

用例 1

输入:

AbCdeFG
3

输出:

5

说明:
根据ASCII码值排序，第三个ASCII码值的字母为F

F在字符串中位置索引为5 (0为字符串的第一个字母位置索引)

用例 2

输入:

fAdDAkBbBq
4

输出:

6

说明:
根据ASCII码值排序前4个字母为AABB由于B重复则只取B的第一个最小位置索引6

而不是第二个B的位置索引8

题目解析

本题是简单的字符串操作题。

2023.05.20 补充了第二个用例

根据第二个用例来看，题目要找的第k个，不是去重+升序后的第k个，而只是排序后的第k个。

详细步骤

1. 读取输入：

   • 读取一个由大小写字母组成的字符串 s。
   • 读取一个整数 k。

2. 创建字符索引映射：

   • 创建一个字典 char_index，键为字符，值为该字符在字符串中的最小索引。
   • 遍历字符串 s，记录每个字符的最小索引。

3. 排序字符：

   • 将字符串 s 中的字符按ASCII码值排序，得到排序后的字符列表 sorted_chars。

4. 查找第K个字符：

   • 如果 k 大于字符串长度，取最大ASCII码值的字符。
   • 否则，取排序后第 k 个字符。

5. 输出结果：

   • 输出该字符在字符串中的最小位置索引。

用例解释

用例 1

• 输入：
  • s = "AbCdeFG"
  • k = 3
• 输出：
  • 5

解释：

• 按ASCII码值排序后的字符列表：['A', 'C', 'd', 'e', 'F', 'G', 'b']
• 第3个字符是 F，其在字符串中的位置索引为 5。

用例 2

• 输入：
  • s = "fAdDAkBbBq"
  • k = 4
• 输出：
  • 6

解释：

• 按ASCII码值排序后的字符列表：['A', 'A', 'B', 'B', 'B', 'D', 'D', 'f', 'k', 'q']
• 第4个字符是 B，其在字符串中的最小位置索引为 6。

通过上述步骤，我们可以高效地求出第K个最小ASCII码值的字母在字符串中的位置索引。这种方法的时间复杂度为 O(n log n)，其中 n 是字符串的长度。

二、JavaScript算法源码

以下是 JavaScript 代码的详细中文注释和逻辑讲解：

---

JavaScript 代码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline"); // 引入 readline 模块，用于读取控制台输入// 创建 readline 接口
const rl = readline.createInterface({input: process.stdin,  // 输入流为标准输入output: process.stdout, // 输出流为标准输出
});// 存储输入行的数组
const lines = [];// 监听输入事件
rl.on("line", (line) => {lines.push(line); // 将每一行输入存入 lines 数组// 当输入行数为 2 时，表示输入完成if (lines.length === 2) {const [str, k] = lines; // 解构赋值，获取输入的两行数据// 调用算法函数并输出结果console.log(getKIndex(str, k));// 清空 lines 数组，以便处理下一组输入lines.length = 0;}
});// 算法函数：获取字符串中第 k 小的字符的索引
function getKIndex(str, k) {// 如果 k 大于字符串长度，则将 k 设置为字符串长度if (k > str.length) k = str.length;// 将字符串转换为数组，排序后获取第 k 小的字符const tar = [...str].sort()[k - 1];// 返回该字符在原字符串中的索引return str.indexOf(tar);
}

---

代码逻辑讲解

1. 输入处理

• 使用 readline 模块读取控制台输入。
• 将每一行输入存入 lines 数组。
• 当 lines 数组的长度为 2 时，表示输入完成，开始处理数据。

---

2. 算法逻辑

• 函数 getKIndex：
  • 参数：
    • str：输入的字符串。
    • k：表示需要查找的第 k 小的字符。
  • 逻辑：
    1. 如果 k 大于字符串长度，则将 k 设置为字符串长度（避免越界）。
    2. 将字符串转换为数组，并对数组进行排序。
    3. 获取排序后数组中第 k - 1 个字符（因为数组索引从 0 开始）。
    4. 返回该字符在原字符串中的索引。

---

3. 示例验证

示例 1：

• 输入：

  hello
  3
  

• 处理过程：
  1. 将字符串 "hello" 转换为数组：['h', 'e', 'l', 'l', 'o']。
  2. 对数组排序：['e', 'h', 'l', 'l', 'o']。
  3. 获取第 3 小的字符：'l'。
  4. 返回 'l' 在原字符串中的索引：2。
• 输出：2。

示例 2：

• 输入：

  world
  5
  

• 处理过程：
  1. 将字符串 "world" 转换为数组：['w', 'o', 'r', 'l', 'd']。
  2. 对数组排序：['d', 'l', 'o', 'r', 'w']。
  3. 获取第 5 小的字符：'w'。
  4. 返回 'w' 在原字符串中的索引：0。
• 输出：0。

---

总结

• 功能：在给定字符串 str 和整数 k 的情况下，找到字符串中第 k 小的字符，并返回其索引。
• 核心逻辑：
  1. 将字符串转换为数组并排序。
  2. 获取排序后数组中第 k - 1 个字符。
  3. 返回该字符在原字符串中的索引。
• 适用场景：需要查找字符串中第 k 小的字符及其索引的场景。
• 注意事项：
  • 如果 k 大于字符串长度，则 k 会被设置为字符串长度。
  • 时间复杂度为 O(n log n)，其中 n 是字符串长度（排序操作的时间复杂度）。

如果有其他问题，欢迎随时提问！

三、Java算法源码

以下是对代码的详细中文注释和讲解：

import java.util.Arrays;  // 导入Arrays类，用于数组操作
import java.util.Scanner; // 导入Scanner类，用于从控制台读取输入public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in); // 创建Scanner对象，用于读取用户输入String str = sc.next(); // 读取用户输入的字符串int k = sc.nextInt();   // 读取用户输入的整数kSystem.out.println(getResult(str, k)); // 调用getResult方法并输出结果}public static int getResult(String str, int k) {char[] chars = str.toCharArray(); // 将字符串转换为字符数组Arrays.sort(chars); // 对字符数组进行排序，按字典序升序排列if (k > str.length()) k = str.length(); // 如果k大于字符串长度，则将k设置为字符串长度char tar = chars[k - 1]; // 获取排序后字符数组中的第k个字符（索引为k-1）return str.indexOf(tar); // 返回该字符在原字符串中的索引位置}
}

代码讲解：

1. 导入类库：

   • import java.util.Arrays;：导入Arrays类，用于对数组进行排序等操作。
   • import java.util.Scanner;：导入Scanner类，用于从控制台读取用户输入。

2. 主方法 main：

   • Scanner sc = new Scanner(System.in);：创建一个Scanner对象，用于读取用户输入。
   • String str = sc.next();：读取用户输入的字符串。
   • int k = sc.nextInt();：读取用户输入的整数k。
   • System.out.println(getResult(str, k));：调用getResult方法，并将结果输出到控制台。

3. getResult 方法：

   • char[] chars = str.toCharArray();：将输入的字符串str转换为字符数组chars。
   • Arrays.sort(chars);：对字符数组chars进行排序，排序后字符数组中的字符按字典序升序排列。
   • if (k > str.length()) k = str.length();：如果输入的k大于字符串的长度，则将k设置为字符串的长度，防止数组越界。
   • char tar = chars[k - 1];：获取排序后字符数组中的第k个字符（由于数组索引从0开始，所以是k-1）。
   • return str.indexOf(tar);：返回该字符在原字符串str中的索引位置。

代码功能总结：

• 该程序的功能是：给定一个字符串和一个整数k，程序会先对字符串中的字符进行排序，然后找到排序后的第k个字符，并返回该字符在原字符串中的索引位置。

示例：

假设输入字符串为"hello"，k为3：

1. 将字符串转换为字符数组：['h', 'e', 'l', 'l', 'o']。
2. 对字符数组进行排序：['e', 'h', 'l', 'l', 'o']。
3. 取第3个字符（索引为2）：'l'。
4. 返回'l'在原字符串"hello"中的索引位置：2。

因此，程序输出为2。

希望这个解释对您理解代码有所帮助！

四、Python算法源码

以下是对代码的详细中文注释和讲解：

# 输入获取
s = input()  # 从控制台读取用户输入的字符串
k = int(input())  # 从控制台读取用户输入的整数k# 算法入口
def getResult(s, k):chars = list(s)  # 将字符串s转换为字符列表chars.sort()  # 对字符列表进行排序，按字典序升序排列if k > len(s):  # 如果k大于字符串的长度k = len(s)  # 将k设置为字符串的长度，防止越界tar = chars[k - 1]  # 获取排序后字符列表中的第k个字符（索引为k-1）return s.index(tar)  # 返回该字符在原字符串s中的索引位置# 调用算法
print(getResult(s, k))  # 调用getResult函数并输出结果

---

代码讲解：

1. 输入获取：

   • s = input()：从控制台读取用户输入的字符串，并赋值给变量s。
   • k = int(input())：从控制台读取用户输入的整数，并赋值给变量k。

2. getResult 函数：

   • chars = list(s)：将字符串s转换为字符列表chars。
   • chars.sort()：对字符列表chars进行排序，排序后字符列表中的字符按字典序升序排列。
   • if k > len(s): k = len(s)：如果输入的k大于字符串的长度，则将k设置为字符串的长度，防止索引越界。
   • tar = chars[k - 1]：获取排序后字符列表中的第k个字符（由于列表索引从0开始，所以是k-1）。
   • return s.index(tar)：返回该字符在原字符串s中的索引位置。

3. 调用算法：

   • print(getResult(s, k))：调用getResult函数，并将结果输出到控制台。

---

代码功能总结：

• 该程序的功能是：给定一个字符串和一个整数k，程序会先对字符串中的字符进行排序，然后找到排序后的第k个字符，并返回该字符在原字符串中的索引位置。

---

示例：

假设输入字符串为"hello"，k为3：

1. 将字符串转换为字符列表：['h', 'e', 'l', 'l', 'o']。
2. 对字符列表进行排序：['e', 'h', 'l', 'l', 'o']。
3. 取第3个字符（索引为2）：'l'。
4. 返回'l'在原字符串"hello"中的索引位置：2。

因此，程序输出为2。

---

注意事项：

1. 索引从0开始：
   • Python中的列表索引从0开始，因此第k个字符的索引是k-1。
2. 越界处理：
   • 如果k大于字符串的长度，程序会将k设置为字符串的长度，避免索引越界。
3. 字符重复：
   • 如果字符串中有重复字符，s.index(tar)会返回第一个匹配字符的索引。

---

希望这个解释对您理解代码有所帮助！

五、C/C++算法源码：

以下是 C语言代码 和 C++代码 的详细中文注释和讲解，并附上代码转换。

---

C语言代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_SIZE 10000  // 定义最大字符串长度// 比较函数，用于qsort排序
int cmp(const void* a, const void* b) {return (*(char*) a) - (*(char*) b);  // 按字符的ASCII值升序排序
}int main() {char s[MAX_SIZE];  // 定义字符数组，用于存储输入的字符串gets(s);  // 从控制台读取字符串（注意：gets不安全，建议使用fgets）int k;scanf("%d", &k);  // 从控制台读取整数kint n = strlen(s);  // 获取字符串的长度char s_cp[n + 1];  // 定义字符数组，用于存储字符串的副本strcpy(s_cp, s);  // 将原字符串复制到副本中qsort(s_cp, n, sizeof(char), cmp);  // 对副本字符串进行排序if (k > n) {  // 如果k大于字符串长度k = n;  // 将k设置为字符串长度，防止越界}char target = s_cp[k - 1];  // 获取排序后字符串的第k个字符（索引为k-1）printf("%lld\n", strchr(s, target) - s);  // 输出目标字符在原字符串中的索引return 0;
}

---

C语言代码讲解：

1. 头文件：

   • #include <stdio.h>：标准输入输出库，用于printf和scanf。
   • #include <stdlib.h>：标准库，用于qsort。
   • #include <string.h>：字符串处理库，用于strlen和strcpy。

2. 宏定义：

   • #define MAX_SIZE 10000：定义最大字符串长度为10000。

3. 比较函数 cmp：

   • 用于qsort排序，按字符的ASCII值升序排列。

4. 主函数 main：

   • char s[MAX_SIZE];：定义字符数组，用于存储输入的字符串。
   • gets(s);：从控制台读取字符串（注意：gets不安全，建议使用fgets）。
   • scanf("%d", &k);：从控制台读取整数k。
   • int n = strlen(s);：获取字符串的长度。
   • char s_cp[n + 1];：定义字符数组，用于存储字符串的副本。
   • strcpy(s_cp, s);：将原字符串复制到副本中。
   • qsort(s_cp, n, sizeof(char), cmp);：对副本字符串进行排序。
   • if (k > n) { k = n; }：如果k大于字符串长度，将k设置为字符串长度。
   • char target = s_cp[k - 1];：获取排序后字符串的第k个字符。
   • printf("%lld\n", strchr(s, target) - s);：输出目标字符在原字符串中的索引。

---

C++代码

#include <iostream>
#include <algorithm>  // 包含sort函数
#include <cstring>    // 包含strlen和strchr函数using namespace std;int main() {char s[10000];  // 定义字符数组，用于存储输入的字符串cin.getline(s, 10000);  // 从控制台读取字符串（安全的方式）int k;cin >> k;  // 从控制台读取整数kint n = strlen(s);  // 获取字符串的长度char s_cp[n + 1];  // 定义字符数组，用于存储字符串的副本strcpy(s_cp, s);  // 将原字符串复制到副本中sort(s_cp, s_cp + n);  // 对副本字符串进行排序if (k > n) {  // 如果k大于字符串长度k = n;  // 将k设置为字符串长度，防止越界}char target = s_cp[k - 1];  // 获取排序后字符串的第k个字符（索引为k-1）cout << (strchr(s, target) - s) << endl;  // 输出目标字符在原字符串中的索引return 0;
}

---

C++代码讲解：

1. 头文件：

   • #include <iostream>：输入输出流库，用于cin和cout。
   • #include <algorithm>：算法库，用于sort函数。
   • #include <cstring>：C风格字符串处理库，用于strlen和strchr。

2. 主函数 main：

   • char s[10000];：定义字符数组，用于存储输入的字符串。
   • cin.getline(s, 10000);：从控制台读取字符串（安全的方式）。
   • cin >> k;：从控制台读取整数k。
   • int n = strlen(s);：获取字符串的长度。
   • char s_cp[n + 1];：定义字符数组，用于存储字符串的副本。
   • strcpy(s_cp, s);：将原字符串复制到副本中。
   • sort(s_cp, s_cp + n);：对副本字符串进行排序。
   • if (k > n) { k = n; }：如果k大于字符串长度，将k设置为字符串长度。
   • char target = s_cp[k - 1];：获取排序后字符串的第k个字符。
   • cout << (strchr(s, target) - s) << endl;：输出目标字符在原字符串中的索引。

---

代码功能总结：

• 该程序的功能是：给定一个字符串和一个整数k，程序会先对字符串中的字符进行排序，然后找到排序后的第k个字符，并返回该字符在原字符串中的索引位置。

---

示例：

假设输入字符串为"hello"，k为3：

1. 将字符串转换为字符数组：['h', 'e', 'l', 'l', 'o']。
2. 对字符数组进行排序：['e', 'h', 'l', 'l', 'o']。
3. 取第3个字符（索引为2）：'l'。
4. 返回'l'在原字符串"hello"中的索引位置：2。

因此，程序输出为2。

---

注意事项：

1. C语言中的gets不安全：
   • 建议使用fgets替代gets，例如：fgets(s, MAX_SIZE, stdin);。
2. C++中的cin.getline：
   • 是安全的输入方式，可以避免缓冲区溢出。
3. 字符重复：
   • 如果字符串中有重复字符，strchr会返回第一个匹配字符的索引。

---

希望这个解释对您理解代码有所帮助！