資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告