字符串筛选排序 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

输入一个由n个大小写字母组成的字符串，按照 ASCII 码值从小到大的排序规则，查找字符串中第 k 个最小ASCII 码值的字母(k>=1) ,

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

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

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

输入描述

第一行输入一个由大小写字母组成的字符串
第二行输入k，k必须大于o，k可以大于输入字符串的长度

输出描述

输出字符串中第k个最小ASCII码值的字母所在字符串的位置索引,
k如果大于字符串长度，则输出最大ASCII值的字母所在字符串的位置索引，
如果第k个最小ascii码值的字母存在重复，则输出该字母的最小位置索引。

示例1

输入：
AbCdeFG
3

输出：
5

说明：
根据 ASCII码值排序，第三个 ASCII码值的字母为F在字符串中位置索引为5 （0 为字符串的一个字母位置索引）

示例2

输入：
fAdDAkBbBq
4

输出：
6

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

题解

这道题属于排序算法的应用，需要根据字符串中字符的ASCII码值进行排序，并根据给定的k值找到对应位置的字符索引。以下是解题思路、代码描述以及时间空间复杂度分析：

解题思路

首先将输入的字符串拆分成字符和对应的索引位置的数组形式，方便后续排序。
对字符数组按照字符的ASCII码值和索引位置进行排序，以满足题目要求的排序规则。
输入k值，如果k大于字符串长度，则直接输出最大ASCII码值的字符所在的位置索引。
否则，找到第k个最小ASCII码值的字符，如果存在重复字符，则输出该字符的最小位置索引。

代码描述

Java代码使用了Scanner进行输入，然后使用List和Collections进行排序和查找。
Python代码通过input()获取输入，使用列表和sort()方法进行排序和查找。
C++代码使用cin进行输入，然后使用vector和sort()函数进行排序和查找。

时间复杂度

时间复杂度为O(nlogn)，其中n为输入字符串的长度，主要由排序算法决定。

空间复杂度

空间复杂度为O(n)，需要额外的空间存储字符和索引位置的数组。

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();

        // 将字符串拆成 <码值，位置索引> 的数组形式，方便后续排序
        List<int[]> arr = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            arr.add(new int[]{s.charAt(i), i});
        }

        // 按照题目要求根据码值和索引位置排序
        Collections.sort(arr, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });

        int k = scanner.nextInt();

        // k 如果大于字符串长度则输出最大 ASCII 码值的字母所在字符串的位置索引
        k = Math.min(k, arr.size());

        int resultIdx = arr.get(k - 1)[1];

        // 如果第 k 个最小 ASCII 码值的字母存在重复，则输出该字母的最小位置索引
        for (int x = 2; k - x >= 0 && arr.get(k - x)[0] == arr.get(k - 1)[0]; x++) {
            resultIdx = arr.get(k - x)[1];
        }
        System.out.println(resultIdx);
    }
}

Python


# 主函数
def main():
    # 输入字符串
    s = input().strip()

    # 将字符串拆成 <码值，位置索引> 的数组形式，方便后续排序
    arr = [(char, index) for index, char in enumerate(s)]

    # 按照题目要求根据码值和索引位置排序
    arr.sort()

    # 输入k
    k = int(input())

    # k 如果大于字符串长度则输出最大 ASCII 码值的字母所在字符串的位置索引
    k = min(k, len(arr))

    result_idx = arr[k - 1][1]

    # 如果第 k 个最小 ASCII 码值的字母存在重复，则输出该字母的最小位置索引
    x = 2
    while k - x >= 0 and arr[k - x][0] == arr[k - 1][0]:
        result_idx = arr[k - x][1]
        x += 1

    print(result_idx)


# 调用主函数
if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s;
    cin >> s;

    // 将字符串拆成 <码值，位置索引> 的数组形式，方便后续排序
    vector<pair<char, int>> arr;
    for (size_t i = 0; i < s.length(); i++) {
        arr.push_back({s[i], i});
    }

    // 按照题目要求根据 码值 和索引位置排序
    sort(arr.begin(), arr.end(), [](pair<char, int> a, pair<char, int> b) {
        if (a.first != b.first) {
            return a.first < b.first;
        } else {
            return a.second < b.second;
        }
    });

    size_t k;
    cin >> k;

    // k 如果大于字符串长度则输出最大 ASCII 码值的字母所在字符串的位置索引
    k = min(k, arr.size());

    size_t result_idx = arr[k - 1].second;

    // 如果第 k 个最小 ASCII 码值的字母存在重复，则输出该字母的最小位置索引
    int x = 2;
    while (k - x >= 0 && arr[k - x].first == arr[k - 1].first) {
        result_idx = arr[k - x].second;
        x++;
    }
    cout << result_idx << endl;

    return 0;
}