目录题目思路Code题目题目内容K-Median 按划分做聚类样本之间用曼哈顿距离L1簇中心取该簇在每一维上的中位数因此离群点不容易把中心拉偏。给定 n 个样本每个样本有 d 个浮点特征。请按下列固定流程把样本分成 k 个簇并输出簇编号、最终中心和 inertia。- 初始化取下标 0 到 k-1 的样本作为 k 个簇的初始中心。- 分配把每个样本分到曼哈顿距离最近的中心。到多个中心的距离相同时分到编号最小的簇。- 更新若某个簇在本轮分配后没有样本则该簇中心保持不变否则用簇内样本在每一维上的中位数替换该簇中心。重复分配与更新直到中心变化量小于 tol或迭代次数达到 max_iter。tol 固定为 10⁻⁴max_iter 固定为 100。中心变化量是所有簇、所有维度上新旧中心坐标绝对差的总和。曼哈顿距离为 dist(x, y) Σᵢ |xᵢ − yᵢ|。一维中位数将数值升序排列后个数为奇数时取正中间的一项个数为偶数时取正中间两项的算术平均可以是浮点数。例如 [1, 3, 5, 9] 的中位数是 (35)/2 4。样例1输入3 2 1 2 8 6 1 4 5输出0 0 0 4.000000 5.000000 11.000000思路整体思路按题面固定流程做 K-Median 迭代模拟——分配曼哈顿距离最近中心平局取最小编号、更新非空簇逐维取中位数空簇中心保持、以全中心绝对变化量之和 1e-4 或迭代满 100 轮为停机条件最后输出簇编号、最终中心与 inertia。1. 初始化把前 k 个样本整行拷贝为初始中心中心与样本分开存储避免更新中心时污染原始特征。2. 每轮分配对每个样本先算到 0 号中心的距离再依次算其余中心只有严格更近才切换簇编号保证并列时落到编号最小的簇。3. 每轮更新非空簇对每一维单独排序取中位数奇数个取正中一项偶数个取中间两项算术平均空簇把旧中心整行原样保留。4. 停机判断所有簇、所有维度上新旧中心坐标绝对差之和用双精度累加小于 1e-4 即停止最多迭代 100 轮。5. 输出最后一轮分配得到的簇编号、停机时的最终中心以及每个样本到所属中心的曼哈顿距离之和inertia。6. 格式中心与 inertia 保留 6 位小数数值为 0 时按正零输出避免打出 -0.000000。复杂度每轮分配 O(n·k·d)更新 O(n·d·log d)逐维排序最多 100 轮总体 O(100·n·k·d)空间 O(n·d)。CodeC#include bits/stdc.h using namespace std; static string fmt6(double x) { // 把一个数格式化为固定 6 位小数的字符串比如 4.1 - 4.100000 // ostringstream 是 C 里先把内容写进内存字符串的工具方便拼接输出 if (x 0) x 0.0; // 把负零(-0.0)统一成正零避免打印 -0.000000 ostringstream oss; oss fixed setprecision(6) x; // fixedsetprecision(6) 保留 6 位小数 return oss.str(); } int main() { int n, d, k; if (!(cin n d k)) return 0; // 第一行样本数 n、维数 d、簇数 k // pts[i] 是第 i 个样本的 d 个特征值 vectorvectordouble pts(n, vectordouble(d)); for (int i 0; i n; i) for (int j 0; j d; j) cin pts[i][j]; // ---- 初始化取前 k 个样本当初始中心 ---- // 这里用迭代器区间拷贝了一份cen 和 pts 是两份独立数据 // 后面更新中心时不会动到原始样本 vectorvectordouble cen(pts.begin(), pts.begin() k); vectorint lab(n, 0); // lab[i] 第 i 个样本所属的簇编号 // ---- 迭代最多 100 轮题目规定 max_iter 100---- for (int iter 0; iter 100; iter) { // ---- 第 1 步分配每个样本归到最近的中心 ---- for (int i 0; i n; i) { double bd 0.0; // best distance到 0 号中心的曼哈顿距离 for (int j 0; j d; j) bd fabs(pts[i][j] - cen[0][j]); int best 0; for (int c 1; c k; c) { double cur 0.0; // 到 c 号中心的距离每维差值绝对值求和 for (int j 0; j d; j) cur fabs(pts[i][j] - cen[c][j]); // 只有严格更近才换簇 而不是 并列时保留编号更小的簇 if (cur bd) { bd cur; best c; } } lab[i] best; } // 按簇归组grp[c] 是 c 号簇里所有样本的下标 vectorvectorint grp(k); for (int i 0; i n; i) grp[lab[i]].push_back(i); // ---- 第 2 步更新非空簇逐维取中位数 ---- vectorvectordouble nxt; // 新中心 double shift 0.0; // 中心变化总量 for (int c 0; c k; c) { if (grp[c].empty()) { // 空簇没有样本中心原样保留题目规定 nxt.push_back(cen[c]); continue; } vectordouble row(d); for (int j 0; j d; j) { // 取出该簇所有样本第 j 维的值 vectordouble vals; for (int idx : grp[c]) vals.push_back(pts[idx][j]); sort(vals.begin(), vals.end()); // 升序排序后取中位数 int m vals.size(); // 奇数个取正中间一个偶数个取中间两个的平均 double med (m % 2 1) ? vals[m / 2] : (vals[m / 2 - 1] vals[m / 2]) / 2.0; row[j] med; } for (int j 0; j d; j) shift fabs(row[j] - cen[c][j]); nxt.push_back(row); } cen nxt; // 用新中心替换旧中心 // ---- 停机判断变化总量 1e-4即 0.0001就提前结束 ---- if (shift 1e-4) break; } // ---- 第 3 步inertia每个样本到所属中心的曼哈顿距离之和 ---- double iner 0.0; for (int i 0; i n; i) for (int j 0; j d; j) iner fabs(pts[i][j] - cen[lab[i]][j]); // ---- 输出第一行簇编号之后 k 行中心最后一行 inertia ---- for (int i 0; i n; i) cout (i ? : ) lab[i]; cout \n; for (int c 0; c k; c) { for (int j 0; j d; j) cout (j ? : ) fmt6(cen[c][j]); cout \n; } cout fmt6(iner) \n; return 0; }Javaimport java.io.*; import java.util.*; public class Solution { static String fmt6(double x) { // 把一个数格式化为固定 6 位小数的字符串比如 4.1 - 4.100000 // Locale.ROOT 保证小数点是 .不会被某些系统的语言设置改成逗号 if (x 0) x 0.0; // 把负零(-0.0)统一成正零避免输出 -0.000000 return String.format(Locale.ROOT, %.6f, x); } static Object[] solve(double[][] pts, int k) { // 整个 K-Median 迭代过程 // 返回 Object[3]{ int[] 簇编号, double[][] 最终中心, Double inertia 总和 } // Java 一个方法只能返回一个值所以把三个结果打包成数组 int n pts.length; // 样本个数 int d pts[0].length; // 每个样本的特征维数 // ---- 初始化取前 k 个样本当初始中心 ---- // clone() 拷贝一份防止后面更新中心时把原始样本改掉 double[][] cen new double[k][]; for (int i 0; i k; i) cen[i] pts[i].clone(); int[] lab new int[n]; // lab[i] 第 i 个样本所属的簇编号 // ---- 迭代最多 100 轮题目规定 max_iter 100---- for (int iter 0; iter 100; iter) { // ---- 第 1 步分配每个样本归到最近的中心 ---- for (int i 0; i n; i) { double bd 0.0; // best distance到 0 号中心的曼哈顿距离 for (int j 0; j d; j) bd Math.abs(pts[i][j] - cen[0][j]); int best 0; for (int c 1; c k; c) { double cur 0.0; // 到 c 号中心的距离每维差值绝对值求和 for (int j 0; j d; j) cur Math.abs(pts[i][j] - cen[c][j]); // 只有严格更近才换簇并列时保留编号更小的簇 if (cur bd) { bd cur; best c; } } lab[i] best; } // 按簇归组grp.get(c) 是 c 号簇里所有样本的下标 ListListInteger grp new ArrayList(); for (int c 0; c k; c) grp.add(new ArrayList()); for (int i 0; i n; i) grp.get(lab[i]).add(i); // ---- 第 2 步更新非空簇逐维取中位数 ---- double[][] nxt new double[k][]; // 新中心 double shift 0.0; // 中心变化总量 for (int c 0; c k; c) { if (grp.get(c).isEmpty()) { // 空簇没有样本中心原样保留 nxt[c] cen[c].clone(); continue; } double[] row new double[d]; for (int j 0; j d; j) { // 收集该簇所有样本第 j 维的值 double[] vals new double[grp.get(c).size()]; int m 0; for (int idx : grp.get(c)) vals[m] pts[idx][j]; Arrays.sort(vals); // 升序排序 // 奇数个取正中间一个偶数个取中间两个的平均 row[j] (vals.length % 2 1) ? vals[vals.length / 2] : (vals[vals.length / 2 - 1] vals[vals.length / 2]) / 2.0; } for (int j 0; j d; j) shift Math.abs(row[j] - cen[c][j]); nxt[c] row; } cen nxt; // 新中心替换旧中心 // ---- 停机判断变化总量 1e-4即 0.0001就提前结束 ---- if (shift 1e-4) break; } // ---- 第 3 步inertia每个样本到所属中心的曼哈顿距离之和 ---- double iner 0.0; for (int i 0; i n; i) for (int j 0; j d; j) iner Math.abs(pts[i][j] - cen[lab[i]][j]); return new Object[]{lab, cen, iner}; } public static void main(String[] args) { // Scanner 是 Java 最方便的读输入工具nextInt/nextDouble 会自动跳过空白 Scanner sc new Scanner(new BufferedInputStream(System.in)); int n sc.nextInt(), d sc.nextInt(), k sc.nextInt(); double[][] pts new double[n][d]; for (int i 0; i n; i) for (int j 0; j d; j) pts[i][j] sc.nextDouble(); Object[] res solve(pts, k); int[] lab (int[]) res[0]; double[][] cen (double[][]) res[1]; double iner (Double) res[2]; // 用 StringBuilder 攒输出最后一次性打印比多次 System.out 快 StringBuilder sb new StringBuilder(); for (int i 0; i n; i) { if (i 0) sb.append( ); sb.append(lab[i]); } sb.append(\n); for (double[] row : cen) { for (int j 0; j d; j) { if (j 0) sb.append( ); sb.append(fmt6(row[j])); } sb.append(\n); } sb.append(fmt6(iner)).append(\n); System.out.print(sb); } }Gopackage main import ( bufio fmt math os sort strconv strings ) func fmt6(x float64) string { // 把一个数格式化为固定 6 位小数的字符串比如 4.1 - 4.100000 // FormatFloat(x, f, 6, 64) 十进制格式、保留 6 位小数、64 位浮点 if x 0 { x 0.0 // 把负零(-0.0)统一成正零避免输出 -0.000000 } return strconv.FormatFloat(x, f, 6, 64) } func solve(pts [][]float64, k int) ([]int, [][]float64, float64) { // 整个 K-Median 迭代过程 // 返回值lab每个样本的簇编号、cen最终中心、inerinertia 总和 n : len(pts) // 样本个数 d : len(pts[0]) // 每个样本的特征维数 // ---- 初始化取前 k 个样本当初始中心 ---- // append([]float64(nil), cen...) 是 Go 里拷贝一份切片的常用写法 // 防止后面更新中心时把原始样本改掉 cen : make([][]float64, k) for i : 0; i k; i { cen[i] append([]float64(nil), pts[i]...) } lab : make([]int, n) // lab[i] 第 i 个样本所属的簇编号 // ---- 迭代最多 100 轮题目规定 max_iter 100---- for iter : 0; iter 100; iter { // ---- 第 1 步分配每个样本归到最近的中心 ---- for i : 0; i n; i { bd : 0.0 // best distance到 0 号中心的曼哈顿距离 for j : 0; j d; j { bd math.Abs(pts[i][j] - cen[0][j]) } best : 0 for c : 1; c k; c { cur : 0.0 // 到 c 号中心的距离每维差值绝对值求和 for j : 0; j d; j { cur math.Abs(pts[i][j] - cen[c][j]) } // 只有严格更近才换簇并列时保留编号更小的簇 if cur bd { bd cur best c } } lab[i] best } // 按簇归组grp[c] 是 c 号簇里所有样本的下标 grp : make([][]int, k) for i : 0; i n; i { grp[lab[i]] append(grp[lab[i]], i) } // ---- 第 2 步更新非空簇逐维取中位数 ---- nxt : make([][]float64, k) // 新中心 shift : 0.0 // 中心变化总量 for c : 0; c k; c { if len(grp[c]) 0 { // 空簇没有样本中心原样保留题目规定 nxt[c] append([]float64(nil), cen[c]...) continue } row : make([]float64, d) for j : 0; j d; j { // 收集该簇所有样本第 j 维的值 vals : make([]float64, 0, len(grp[c])) for _, idx : range grp[c] { vals append(vals, pts[idx][j]) } sort.Float64s(vals) // 升序排序Go 自带的浮点排序 // 奇数个取正中间一个偶数个取中间两个的平均 m : len(vals) if m%2 1 { row[j] vals[m/2] } else { row[j] (vals[m/2-1] vals[m/2]) / 2.0 } } for j : 0; j d; j { shift math.Abs(row[j] - cen[c][j]) } nxt[c] row } cen nxt // 新中心替换旧中心 // ---- 停机判断变化总量 1e-4即 0.0001就提前结束 ---- if shift 1e-4 { break } } // ---- 第 3 步inertia每个样本到所属中心的曼哈顿距离之和 ---- iner : 0.0 for i : 0; i n; i { for j : 0; j d; j { iner math.Abs(pts[i][j] - cen[lab[i]][j]) } } return lab, cen, iner } func main() { // 把整个输入读进来按空白切分不用逐行解析 data, _ : bufio.NewReader(os.Stdin).ReadToEnd() fields : strings.Fields(string(data)) p : 0 // 当前读到第几个字段 // atoi/atof读一个整数/浮点数并把指针后移闭包写法省去到处传 p atoi : func() int { v, _ : strconv.Atoi(fields[p]); p; return v } atof : func() float64 { v, _ : strconv.ParseFloat(fields[p], 64); p; return v } n, d, k : atoi(), atoi(), atoi() // 样本数、维数、簇数 pts : make([][]float64, n) for i : 0; i n; i { pts[i] make([]float64, d) for j : 0; j d; j { pts[i][j] atof() } } lab, cen, iner : solve(pts, k) // bufio.Writer 攒着一起写比每次直接 fmt.Print 快很多 w : bufio.NewWriter(os.Stdout) defer w.Flush() // 函数结束前把缓冲区内容真正输出 for i, v : range lab { if i 0 { fmt.Fprint(w, ) } fmt.Fprint(w, v) } fmt.Fprintln(w) for _, row : range cen { for j, v : range row { if j 0 { fmt.Fprint(w, ) } fmt.Fprint(w, fmt6(v)) } fmt.Fprintln(w) } fmt.Fprintln(w, fmt6(iner)) }C#include stdio.h #include stdlib.h #include string.h #include math.h /* 把一个数格式化为固定 6 位小数的字符串比如 4.1 - 4.100000 C 语言没有方便的小数格式化返回值所以写进 buf调用者给的字符数组 */ static void fmt6(char *buf, double x) { if (x 0) x 0.0; /* 把负零(-0.0)统一成正零避免打印 -0.000000 */ sprintf(buf, %.6f, x); /* %.6f 就是保留 6 位小数 */ } /* qsort 需要的比较函数返回负数表示 a 排前面正数表示 b 排前面 */ static int cmpd(const void *a, const void *b) { double x *(const double *)a, y *(const double *)b; return (x y) - (x y); } int main(void) { int n, d, k; if (scanf(%d %d %d, n, d, k) ! 3) return 0; /* 样本数、维数、簇数 */ /* C 语言没有动态数组用 malloc 申请一块连续内存当二维表用 pts[i*dj] 就是第 i 个样本的第 j 维把二维压平成一维存 */ double *pts (double *)malloc(sizeof(double) * n * d); for (int i 0; i n * d; i) scanf(%lf, pts[i]); /* 中心也用同样方式存cen[c*dj] 是 c 号中心的第 j 维 */ double *cen (double *)malloc(sizeof(double) * k * d); double *nxt (double *)malloc(sizeof(double) * k * d); /* 初始化前 k 个样本直接拷贝当初始中心 memcpy 内存拷贝相当于把 pts 的前 k*d 个数复制到 cen */ memcpy(cen, pts, sizeof(double) * k * d); int *lab (int *)malloc(sizeof(int) * n); /* lab[i] 第 i 个样本的簇编号 */ int *cnt (int *)malloc(sizeof(int) * k); /* cnt[c] c 号簇里有多少样本 */ double *vals (double *)malloc(sizeof(double) * n); /* 取中位数用的临时数组 */ /* ---- 迭代最多 100 轮题目规定 max_iter 100---- */ for (int iter 0; iter 100; iter) { /* ---- 第 1 步分配每个样本归到最近的中心 ---- */ for (int i 0; i n; i) { double bd 0.0; /* best distance到 0 号中心的曼哈顿距离 */ for (int j 0; j d; j) bd fabs(pts[i * d j] - cen[j]); int best 0; for (int c 1; c k; c) { double cur 0.0; /* 到 c 号中心的距离每维差值绝对值求和 */ for (int j 0; j d; j) cur fabs(pts[i * d j] - cen[c * d j]); /* 只有严格更近才换簇并列时保留编号更小的簇 */ if (cur bd) { bd cur; best c; } } lab[i] best; } /* 统计每个簇的样本个数顺便用来判断空簇 */ memset(cnt, 0, sizeof(int) * k); /* memset 把数组全部清零 */ for (int i 0; i n; i) cnt[lab[i]]; /* ---- 第 2 步更新非空簇逐维取中位数 ---- */ double shift 0.0; /* 中心变化总量 */ for (int c 0; c k; c) { if (cnt[c] 0) { /* 空簇没有样本中心原样保留题目规定 */ memcpy(nxt[c * d], cen[c * d], sizeof(double) * d); continue; } for (int j 0; j d; j) { /* 收集该簇所有样本第 j 维的值遍历所有样本挑出属于 c 簇的 */ int m 0; for (int i 0; i n; i) if (lab[i] c) vals[m] pts[i * d j]; qsort(vals, m, sizeof(double), cmpd); /* 升序排序 */ /* 奇数个取正中间一个偶数个取中间两个的平均 */ double med (m % 2 1) ? vals[m / 2] : (vals[m / 2 - 1] vals[m / 2]) / 2.0; nxt[c * d j] med; } for (int j 0; j d; j) shift fabs(nxt[c * d j] - cen[c * d j]); } memcpy(cen, nxt, sizeof(double) * k * d); /* 新中心替换旧中心 */ /* ---- 停机判断变化总量 1e-4即 0.0001就提前结束 ---- */ if (shift 1e-4) break; } /* ---- 第 3 步inertia每个样本到所属中心的曼哈顿距离之和 ---- */ double iner 0.0; for (int i 0; i n; i) for (int j 0; j d; j) iner fabs(pts[i * d j] - cen[lab[i] * d j]); /* ---- 输出第一行簇编号之后 k 行中心最后一行 inertia ---- */ for (int i 0; i n; i) printf(i ? %d : %d, lab[i]); printf(\n); char buf[64]; for (int c 0; c k; c) { for (int j 0; j d; j) { fmt6(buf, cen[c * d j]); printf(j ? %s : %s, buf); } printf(\n); } fmt6(buf, iner); printf(%s\n, buf); /* malloc 申请的内存要手动释放好习惯程序结束也会自动回收 */ free(pts); free(cen); free(nxt); free(lab); free(cnt); free(vals); return 0; }Pythondef fmt6(x): # 把一个数格式化为固定 6 位小数的字符串比如 4.1 - 4.100000 # 题目要求中心和inertia都保留 6 位小数所以所有浮点数输出前都要经过它 if x 0: # 小知识浮点运算可能算出负零(-0.0)直接打印会变成 -0.000000 # 这里把任何等于 0 的数包括 -0.0统一改成正零 0.0 x 0.0 return format(x, .6f) def solve(pts, k): # 整个 K-Median 迭代过程都在这里完成 # pts 是所有样本点二维列表pts[i] 是第 i 个样本的 d 个特征值 # k 是要聚成的簇数 # 返回三个结果lab每个样本的簇编号、cen最终中心、inerinertia 总和 n len(pts) # 样本个数 d len(pts[0]) # 每个样本的特征维数 # ---- 初始化取前 k 个样本当初始中心 ---- # 注意必须拷贝一份不能直接引用 pts[i] # 否则后面更新中心时会把原始样本数据也改掉导致距离算错 cen [pts[i][:] for i in range(k)] # lab[i] 记录第 i 个样本被分到了哪个簇0 ~ k-1 lab [0] * n # ---- 迭代最多 100 轮题目规定 max_iter 100---- for _ in range(100): # ---- 第 1 步分配Assignment---- # 把每个样本分到曼哈顿距离最近的中心 for i in range(n): pi pts[i] # 当前样本 bd 0.0 # best distance当前已知的最短距离 for j in range(d): # 曼哈顿距离 每一维差值的绝对值再求和 # 比如 (1,2) 到 (4,6) 的距离是 |1-4| |2-6| 3 4 7 bd abs(pi[j] - cen[0][j]) best 0 # 目前最近的簇编号先假设是 0 号簇 for c in range(1, k): cur 0.0 # 当前样本到 c 号中心的距离 for j in range(d): cur abs(pi[j] - cen[c][j]) # 关键只有严格更近才换簇用 而不是 # 这样当两个中心距离并列时样本会留在编号更小的簇符合题意 if cur bd: bd cur best c lab[i] best # 按簇编号把样本的下标归组grp[c] 就是 c 号簇里所有样本的下标列表 grp [[] for _ in range(k)] for i in range(n): grp[lab[i]].append(i) # ---- 第 2 步更新Update---- nxt [] # 存放更新后的新中心 shift 0.0 # 中心变化量所有簇、所有维度新旧坐标绝对差的总和 for c in range(k): if not grp[c]: # 空簇这一轮没有任何样本分到它中心原样保留题目规定 nxt.append(cen[c][:]) continue row [] # c 号簇的新中心一共 d 维 for j in range(d): # 收集该簇所有样本在第 j 维上的取值排序后取中位数 vals sorted(pts[i][j] for i in grp[c]) m len(vals) if m % 2 1: # 奇数个取正中间那一个 med vals[m // 2] else: # 偶数个取中间两个的算术平均题目规定可以是小数 med (vals[m // 2 - 1] vals[m // 2]) / 2.0 row.append(med) for j in range(d): # 累加这一簇每一维的变化量用于判断要不要继续迭代 shift abs(row[j] - cen[c][j]) nxt.append(row) cen nxt # 用新中心替换旧中心进入下一轮 # ---- 停机判断变化量之和小于 tol1e-4 就提前结束 ---- if shift 1e-4: break # ---- 第 3 步计算 inertia ---- # inertia 每个样本到自己所属簇中心的曼哈顿距离之和 # 注意用停机那一刻的 lab最后一次分配结果和 cen最后一次更新后的中心 iner 0.0 for i in range(n): for j in range(d): iner abs(pts[i][j] - cen[lab[i]][j]) return lab, cen, iner def main(): import sys # 把整个输入读进来按空白切分比逐行读更省事也不用担心换行格式 data sys.stdin.read().split() it iter(data) # 第一行三个数样本数 n、维数 d、簇数 k n, d, k int(next(it)), int(next(it)), int(next(it)) # 接下来 n 行每行 d 个浮点数是每个样本的特征值 pts [[float(next(it)) for _ in range(d)] for _ in range(n)] lab, cen, iner solve(pts, k) # 输出三部分第一行所有样本的簇编号然后 k 行中心最后一行 inertia lines [ .join(map(str, lab))] for row in cen: lines.append( .join(fmt6(v) for v in row)) lines.append(fmt6(iner)) sys.stdout.write(\n.join(lines) \n) if __name__ __main__: main()