找到一个点,以使C ++中的曼哈顿距离之和最小
假设我们在K维空间中有n个不同的点,n的值在(2,105)范围内,k的值在(1到5)范围内。我们必须确定点,以使从合成点到n个点的曼哈顿距离之和最小。
两点P1(x1,y1)和P2(x2,y2)之间的曼哈顿距离为|x1–x2|+|y1–y2|。假设维度为3,并且有三个点,例如(1、1、1),(2、2、2),(3、3、3),则输出将为(2、2、2)。
为了解决这个问题,我们必须对所有K个维度中的点进行排序,并从k个维度中的每个中间元素获取输出。
示例
#include<iostream> #include<vector> #include<cmath> #include<algorithm> using namespace std; void minimizeHanhattan(int n, int k, vector<vector<int> >& pointList) { for (int i = 0; i < k; ++i) //sort in all k dimension sort(pointList[i].begin(), pointList[i].end()); for (int i = 0; i < k; ++i) cout << pointList[i][(ceil((double)n / 2) - 1)] << " "; } int main() { int n = 4, k = 4; vector<vector<int> > point = { { 1, 5, 2, 4 }, { 6, 2, 0, 6 }, { 9, 5, 1, 3 }, { 6, 7, 5, 9 } }; minimizeHanhattan(n, k, point); }
输出结果
2 2 3 6