找到一个点，以使C ++中的曼哈顿距离之和最小

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们在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

以上是 找到一个点，以使C ++中的曼哈顿距离之和最小 的全部内容， 来源链接： utcz.com/z/351429.html

回到顶部