数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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
更新于: 2019年10月24日
539 次浏览
广告