给你出道题:依次去掉离中心最远的M个点

给定一个数组a[N],里面包含N个向量。现在要求进行删点操作,删点原则如下:
1、求出N个向量的中心O1,删除离O1最远的那个点
2、求出N-1个向量的中心O2,删除O2最远的那个点
......
重复以上步骤,直到删掉M个点(N>M)。
求最后剩下的数组。

首先,这个问题答案可能不唯一。如果有两个最远点,删除哪一个会深刻影响后续的删点过程。如果坚持不改这个问题,那么最后得到的是一个有向无环图。
如果添加一个条件,保证不会产生多个最远点。那么这个问题就很准确了。
求中心可以维护总和和点的个数两个变量来直接计算,而不用每次删完点之后都求平均。
求最远点问题相当于给定一个图,求图中离点x最远的点。

用python简单实现一下这道题的“出题器”。

import numpy as np

# 一个随机数组
a = np.random.rand(100, 10)
pre = 10  # 删掉的点数

ans = []
na = np.copy(a)
while len(ans) < pre:
    m = np.mean(na, 0)
    d = np.linalg.norm(na - m, ord=2, axis=1)
    di = max([(i, d[i]) for i in range(len(d))])
    ans.append(na[di[0]])
    na = np.append(na[:di[0]], na[di[0] + 1:], 0)
print(ans)
原文地址:https://www.cnblogs.com/weiyinfu/p/7609971.html