华为 · 排序 · 算法编程题
华为 排序 n ≤ 1e3 时限 1 秒 / 32 MB

题目描述

定义一个字符串 s 的“兄弟单词”为:将 s 重新排序后得到的与原字符串不同的新字符串。
现在,对于给定的 n 个字符串 s_1, s_2, ..., s_n 和另一个单独的字符串 x ,你需要解决两个问题:
统计这 n 个字符串中,有多少个是 x 的“兄弟单词”(注意,这 n 个字符串可能有重复,重复字符串分别计数);
将这 n 个字符串中 x 的“兄弟单词”按字典序从小到大排序,输出排序后的第 k 个兄弟单词(从 1 开始计数)。特别地,如果不存在,则不输出任何内容。
【名词解释】
从字符串的第一个字符开始逐个比较,直至发现第一个不同的位置,比较这个位置字符的字母表顺序,字母序较小的字符串字典序也较小;如果比较到其中一个字符串的结尾时依旧全部相同,则较短的字符串字典序更小。

输入输出

输入描述
在一行上依次输入:
一个整数 n (1 ≤ n ≤ 10^3) 代表字符串的个数;
n 个长度为 1 ≤ length(s_i) ≤ 10 ,仅由小写字母构成的字符串 s_1, s_2, ..., s_n ;
一个长度为 1 ≤ length(x) ≤ 10 ,仅由小写字母构成的字符串 x ;
一个整数 k (1 ≤ k ≤ n) 代表要查找的第 k 小的兄弟单词的序号。
输出描述
第一行输出一个整数,代表给定的 n 个字符串中, x 的“兄弟单词”的数量;
第二行输出一个字符串,代表将给定的 n 个字符串中 x 的“兄弟单词”按字典序排序后的第 k 小兄弟单词。特别地,如果不存在,则不输出任何内容(完全省略第二行)。

样例共 2 组

样例 1 · 在这个样例中, x 的兄弟单词为 "acb" 、 "bac" 、 " orangebca " 、 " orangecab " 、 "cba" 。其中,标橙色的两个字符串存在于所给定的 n 个字符串中。第 1 小的兄弟单词为 "bca" 。
输入
3 abc bca cab abc 1
输出
2
bca
样例 2 · 在这个样例中,按照定义,字符串 "a" 没有兄弟单词。
输入
3 a aa aaa a 1
输出
0

算法解析依据充分

考点:字符串 · 排序

数据规模 n ≤ 1e3 | 限制 1 秒 / 32MB | 标准输入输出

题目画像

  • 数据规模:n ≤ 1e3
  • 元素值域:s_i ≤ 10,x ≤ 10(注意整数类型选择,避免溢出)
  • 复杂度门槛:允许 O(n²);若 n ≤ 300,O(n³) 通常也跑得动,需看具体常数。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:排序

先用 O(n log n) 排序把无序变有序,后续处理往往就简单了。

思路框架(排序 通法 · 非本题专属)

  1. 排序后很多性质变简单:相邻关系、前缀性质、二分可行。
  2. 若题目禁止使用排序库函数,则手写快排/归并(归并还能顺带求逆序对)。
  3. 排序常与其他范式组合,比如「排序 + 贪心」「排序 + 二分」「排序 + 双指针」。

实现要点:在 C++ 中用 std::sort,Python 用 sorted();注意自定义比较函数的严格弱序。

复杂度:时间 O(n log n) | 空间 O(log n) ~ O(n)

该范式的通法易错点

  • 自定义比较函数不满足严格弱序会导致运行时崩溃。
  • 排序后丢失原始下标,题目需要下标时记得用 pair 一起排。

对照本题

  • 数据规模 n ≤ 1e3,允许 O(n²);若 n ≤ 300,O(n³) 通常也跑得动,需看具体常数。
  • 元素值域最大到 10 —— 求和 / 相乘时记得开 64 位整数。

题目给出的提示

  • 这 n 个字符串可能有重复,重复字符串分别计数)

样例解读

样例 1:输入 3 abc bca cab abc 1 → 输出 2 / bca

在这个样例中, x 的兄弟单词为 "acb" 、 "bac" 、 " orangebca " 、 " orangecab " 、 "cba" 。其中,标橙色的两个字符串存在于所给定的 n 个字符串中。第 1 小的兄弟单词为 "bca" 。

样例 2:输入 3 a aa aaa a 1 → 输出 0

在这个样例中,按照定义,字符串 "a" 没有兄弟单词。

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:华为机试编程模拟题2。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解