华为 · 排序 · 算法编程题
华为 排序 N ≤ 20 时限 1 秒 / 256 MB

题目描述

小红需要把多组等长传感器信号按频域特征聚类。
对每组长度为 L 的信号计算 DFT，在 k=1 到 L/2-1 中按幅值从大到小选前三个频率下标，幅值相同时选择较小下标，依次组成三维整数特征。
随后对这些特征执行 K-Means。输入给出 K 个原信号下标作为初始中心。每轮将特征分配给欧氏距离最近的中心，距离相同时选择编号较小的中心；新中心为簇内各维均值按银行家舍入取整。空簇保持原中心。中心全部不变或完成 100 轮后停止。
最后把 K 个中心按字典序排序输出。

输入输出

输入描述
第一行输入 N,L,K 。接下来 N 行每行 L 个浮点数，最后一行输入 K 个互不相同的初始中心下标。
保证 9 ≤ N ≤ 20 ， 8 ≤ L ≤ 50 且 L 为偶数， 2 ≤ K ≤ 4 ，下标在 [0,N-1] 内。
输出描述
输出 K 行排序后的聚类中心，每行三个整数。

样例共 1 组

样例 1 · 所有频率幅值相等，按下标选择 1、2、3；两个中心相同且保持不变。
输入
9 8 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1
输出
1 2 3
1 2 3

算法解析依据一般

考点：排序

数据规模 N ≤ 20 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 20，K ≤ 4
  • 元素值域：L ≤ 50（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：排序

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

思路框架（排序 通法 · 非本题专属）

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

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

复杂度：时间 O(n log n) ｜ 空间 O(log n) ~ O(n)

该范式的通法易错点

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

对照本题

  • 数据规模 N ≤ 20，允许指数级做法：暴力枚举全部子集 2^n / 回溯搜索 / 状压 DP。
  • 元素值域最大到 50 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 9 8 2 / 0 0 0 0 0 0 0 0 / 0 0 0 0 0 0 0 0 / 0 0 0 0 0 0 0 0 / 0 0 0 0 0 0 0 0 / 0 0 0 0 0 0 0 0 / 0 → 输出 1 2 3 / 1 2 3

所有频率幅值相等，按下标选择 1、2、3；两个中心相同且保持不变。

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

本题来源：2026年-华为-06月17号AI岗。

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