解题思路

这是一道字符串处理题目,主要思路如下:

  1. 统计字符出现次数:

    • 使用数组记录每个ASCII字符出现的次数
    • 数组大小为127即可覆盖所有ASCII字符
  2. 查找第k个只出现一次的字符:

    • 按顺序遍历字符串
    • 当遇到出现次数为1的字符时,计数器加1
    • 当计数器等于 时,找到目标字符
  3. 输出处理:

    • 如果找到目标字符,输出[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]]))

算法及复杂度

  • 算法:哈希统计
  • 时间复杂度: - 其中 为字符串长度
  • 空间复杂度: - 使用固定大小的数组存储字符计数