解题思路
这是一道字符串处理题目,主要思路如下:
-
统计字符出现次数:
- 使用数组记录每个ASCII字符出现的次数
- 数组大小为127即可覆盖所有ASCII字符
-
查找第k个只出现一次的字符:
- 按顺序遍历字符串
- 当遇到出现次数为1的字符时,计数器加1
- 当计数器等于
时,找到目标字符
-
输出处理:
- 如果找到目标字符,输出[c]格式
- 如果没有找到,输出"Myon~"
代码
#include <iostream>
#include <string>
using namespace std;
int main() {
int k;
string str;
while(cin >> k) {
cin.ignore(); // 忽略换行符
getline(cin, str);
// 统计字符出现次数
int count[127] = {0};
for(char c : str) {
count[c]++;
}
// 查找第k个只出现一次的字符
int found = 0;
int kth = 0;
for(char c : str) {
if(count[c] == 1) {
kth++;
if(kth == k) {
cout << "[" << c << "]" << endl;
found = 1;
break;
}
}
}
// 如果没找到,输出Myon~
if(!found) {
cout << "Myon~" << endl;
}
}
return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String input = null;
while ((input=bf.readLine()) != null) {
int spilt = input.indexOf(" ");
int k = Integer.parseInt(input.substring(0,spilt));
String str = input.substring(spilt+1);
String res = helper(str, k);
System.out.println(res);
}
}
// 由于字符都在ASCII里面,就创建一个数组,表示出现的次数
public static String helper(String str, int k) {
char[] c = str.toCharArray();
int[] count = new int[255];
for (int i = 0; i < c.length; i++) {
count[c[i]]++;
}
// 找到第k个只出现一次的字符
int cnt = 0;
for (int i = 0; i < c.length; i++) {
if (count[c[i]] == 1) {
cnt++;
}
if (cnt == k) {
return "[" + c[i]+"]";
}
}
return "Myon~";
}
}
import sys
from collections import Counter
for line in sys.stdin:
line=line.strip('\n')
i=0
while line[i]!=' ':
i+=1
K = int(line[:i])
strs = line[i+1:]
counter = Counter(strs)
ones = [k for k, v in counter.items() if v == 1]
if len(ones) < K:
print('Myon~')
else:
ones_i = []
for k in ones:
ones_i.append(strs.find(k))
ones_i = sorted(ones_i)
print('[{}]'.format(strs[ones_i[K - 1]]))
算法及复杂度
- 算法:哈希统计
- 时间复杂度:
- 其中
为字符串长度
- 空间复杂度:
- 使用固定大小的数组存储字符计数