当前位置：首页 > article >正文

机试题——第k大字母

article 2025/2/9 6:50:29

题目描述

曾经有一个程序员，他正在为他的代码编写一个排序算法。他正在编写一个程序，该程序需要在字符串中查找第k个最小的ASCII码字母。他认为这是一个有趣的挑战，因为他要解决的问题涉及到字符串和排序，这些都是他喜欢的计算机科学领域。他经过一番研究后，终于开发出了一个能够解决这个问题的程序。

该程序接受一个由n个大小写字母组成的字符串及一个整数k作为输入，按照ASCII码值从小到大的排序规则查找字符串中第k个最小ASCII码值的字母。如果k大于字符串长度，则输出最大ASCII值的字母所在字符串的位置索引（字符串的第一个字符位置索引为0），如果有重复的字母，则输出字母的最小位置索引。现在，塔子哥的程序被广泛应用于各种排序任务中。

输入描述

输入包含两行：

第一行是一个字符串 ( S )，由大小写字母组成，长度不超过100。
第二行是一个整数 ( k )，表示需要查找的第k个最小ASCII码字母的位置索引。

输出描述

输出一个整数，表示第k个最小ASCII码字母在字符串中的位置索引（从0开始）。如果 ( k ) 大于字符串的长度，则输出最大ASCII值的字母所在字符串的位置索引。

用例输入

kjahah
4

解题思路

本题的目标是找到字符串中第k个最小的ASCII码字母的位置索引。主要步骤如下：

记录每个字符的首次出现位置和计数：
- 使用两个数组fir和cot分别记录每个字符的首次出现位置和出现次数。
- 遍历字符串，更新每个字符的首次出现位置和计数。
处理特殊情况：
- 如果 ( k ) 大于字符串的长度，直接输出最大ASCII值的字母的位置索引。
查找第k个最小的ASCII码字母：
- 遍历所有可能的ASCII码值（从0到255），累加每个字符的计数，直到累加值大于等于 ( k )。
- 输出该字符的首次出现位置。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <string>
#include <stack>
#include <algorithm>
#include <map>
#include <iomanip>
using namespace std;
#define msize  105

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string input;
    getline(cin, input); // 读取字符串
    vector<int> fir(256, -1); // 记录每个字符的首次出现位置
    vector<int> cot(256, 0);  // 记录每个字符的出现次数
    for (int i = 0; i < input.size(); i++) {
        if (fir[input[i]] == -1) fir[input[i]] = i; // 更新首次出现位置
        cot[input[i]]++; // 更新出现次数
    }
    int k;
    cin >> k; // 读取k值
    if (k >= input.size()) {
        // 如果k大于字符串长度，输出最大ASCII值的字母的位置索引
        for (int i = 255; i >= 0; i--) {
            if (fir[i] != -1) {
                cout << fir[i];
                return 0;
            }
        }
    }
    int cur = 0; // 当前累加的字符数量
    for (int i = 0; i < 256; i++) {
        cur += cot[i]; // 累加当前字符的出现次数
        if (cur >= k) {
            cout << fir[i]; // 输出第k个最小的ASCII码字母的位置索引
            return 0;
        }
    }
    return 0;
}