华为OD机试真题 - 字符串筛选排序 (C++ Python JAVA JS GO)

字符串筛选排序

2025华为OD机试 - 华为OD上机考试 100分题型

华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解

题目描述

输入一个由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码值的字母为FF在字符串中位置索引为5(0为字符串的第一个字母位置索引)

用例2

输入

fAdDAkBbBq 4

输出

6

说明

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

题解

思路：哈希表 + 自定义排序

1. 使用哈希表统计每个字符出现的最小序号。
2. 将原字符串进行升序排序。
3. 如果k > input.size(), 设置k = input.size()
4. 利用之前的哈希表输出排序后对应字符首次出现的位置。

c++

#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; int main() { string input; getline(cin, input); int k; cin >> k; // 记录每个字符出现最小序号 map<char, int> charFirstPos; int n = input.size(); for (int i = 0; i < n; i++) { char c = input[i]; if (charFirstPos.find(c) == charFirstPos.end()) { charFirstPos[c] = i; } } // 升序 sort(input.begin(), input.end()); // 指向最大ASCII if (k > n) { k = n; } // 输出结果 cout << charFirstPos[input[k - 1]]; return 0; }

JAVA

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine(); int k = Integer.parseInt(br.readLine()); // 记录每个字符第一次出现的位置 Map<Character, Integer> charFirstPos = new HashMap<>(); int n = input.length(); for (int i = 0; i < n; i++) { char c = input.charAt(i); if (!charFirstPos.containsKey(c)) { charFirstPos.put(c, i); } } // 转为字符数组并按 ASCII 升序排序 char[] chars = input.toCharArray(); Arrays.sort(chars); if (k > n) k = n; // 输出排序后第 k 个字符在原串中的最小下标 System.out.println(charFirstPos.get(chars[k - 1])); } }

Python

# 读取输入s=input().rstrip()k=int(input())# 记录每个字符第一次出现的位置char_first_pos={}fori,cinenumerate(s):ifcnotinchar_first_pos:char_first_pos[c]=i# 按 ASCII 升序排序chars=sorted(s)n=len(s)ifk>n:k=n# 输出结果print(char_first_pos[chars[k-1]])

JavaScript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on('line',line=>{lines.push(line.trim());});rl.on('close',()=>{constinput=lines[0];letk=parseInt(lines[1]);// 记录每个字符第一次出现的位置constcharFirstPos=newMap();for(leti=0;i<input.length;i++){constc=input[i];if(!charFirstPos.has(c)){charFirstPos.set(c,i);}}// 按 ASCII 升序排序constchars=input.split('').sort();if(k>input.length)k=input.length;// 输出结果console.log(charFirstPos.get(chars[k-1]));});

Go

packagemainimport("bufio""fmt""os""sort")funcmain(){in:=bufio.NewReader(os.Stdin)varinputstringfmt.Fscanln(in,&input)varkintfmt.Fscanln(in,&k)// 记录每个字符第一次出现的位置charFirstPos:=make(map[rune]int)fori,c:=rangeinput{if_,ok:=charFirstPos[c];!ok{charFirstPos[c]=i}}// 按 ASCII 升序排序chars:=[]rune(input)sort.Slice(chars,func(i,jint)bool{returnchars[i]<chars[j]})n:=len(chars)ifk>n{k=n}// 输出结果fmt.Println(charFirstPos[chars[k-1]])}