You are given two 0-indexed integer arrays nums1 and nums2 of the same length. A pair of indices (i,j) is called beautiful if|nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| is the smallest amongst all possible indices pairs where i < j.
Return the beautiful pair. In the case that there are multiple beautiful pairs, return the lexicographically smallest pair.
Note that
|x| denotes the absolute value of x.
A pair of indices (i1, j1) is lexicographically smaller than (i2, j2) if i1 < i2 or i1 == i2 and j1 < j2.
Input: nums1 =[1,2,3,2,4], nums2 =[2,3,1,2,3]Output: [0,3]Explanation: Consider index 0 and index 3. The value of |nums1[i]-nums1[j]|+|nums2[i]-nums2[j]|is1, which is the smallest value we can achieve.
Example 2:
1
2
3
Input: nums1 =[1,2,4,3,2,5], nums2 =[1,4,2,3,5,1]Output: [1,4]Explanation: Consider index 1 and index 4. The value of |nums1[i]-nums1[j]|+|nums2[i]-nums2[j]|is1, which is the smallest value we can achieve.
The Manhattan distance |a-b|+|c-d| can be minimized by sorting points and checking nearby points. By transforming coordinates and using an ordered set (like TreeSet or SortedList), we can efficiently find the closest pair.
#include<set>classSolution {
public: vector<int> beautifulPair(vector<int>& a, vector<int>& b) {
int n = a.size(), minDist = INT_MAX;
vector<tuple<int,int,int>> pts;
for (int i =0; i < n; ++i) pts.push_back({a[i], b[i], i});
sort(pts.begin(), pts.end());
set<pair<int,int>> s;
vector<int> ans = {0, 1};
for (auto& [x, y, i] : pts) {
auto it = s.lower_bound({y, -1});
for (int d =-1; d <=0; ++d) {
auto jt = it;
if (d ==-1&& jt != s.begin()) --jt;
if (jt != s.end()) {
int j = jt->second;
int dist = abs(a[i]-a[j]) + abs(b[i]-b[j]);
if (i > j && (dist < minDist || (dist == minDist && make_pair(j,i) < make_pair(ans[0],ans[1])))) {
minDist = dist;
ans = {j, i};
}
}
}
s.insert({y, i});
}
return ans;
}
};
classSolution {
funbeautifulPair(a: IntArray, b: IntArray): IntArray {
val n = a.size
val pts = Array(n) { i -> Triple(a[i], b[i], i) }
pts.sortWith(compareBy({ it.first }, { it.second }, { it.third }))
var ans = intArrayOf(0, 1)
var minDist = Int.MAX_VALUE
val s = sortedMapOf<Int, Int>()
for ((x, y, i) in pts) {
for ((yy, j) in s) {
val dist = kotlin.math.abs(a[i]-a[j]) + kotlin.math.abs(b[i]-b[j])
if (i > j && (dist < minDist || (dist == minDist && (j < ans[0] || (j == ans[0] && i < ans[1]))))) {
minDist = dist
ans = intArrayOf(j, i)
}
}
s[y] = i
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution:
defbeautifulPair(self, a: list[int], b: list[int]) -> list[int]:
n = len(a)
pts = sorted((a[i], b[i], i) for i in range(n))
ans = [0, 1]
min_dist = float('inf')
from bisect import bisect_left, insort
s = []
for x, y, i in pts:
for yy, j in s:
dist = abs(a[i]-a[j]) + abs(b[i]-b[j])
if i > j and (dist < min_dist or (dist == min_dist and (j < ans[0] or (j == ans[0] and i < ans[1])))):
min_dist = dist
ans = [j, i]
insort(s, (y, i))
return ans