2613：美数对（★★）

2023-04-03 约 437 字预计阅读 1 分钟次阅读

力扣第 2613 题

题目

给定两个长度相同的 下标从 0 开始 的整数数组 nums1 和 nums2 ，如果 |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| 在所有可能的下标对中是最小的，其中 i < j ，则称下标对 (i,j) 为美数对，

返回美数对。如果有多个美数对，则返回字典序最小的美数对。

注意：

|x| 表示 x 的绝对值。
一对索引 (i1, j1) 在字典序意义下小于 (i2, j2) ，当且仅当 i1 < i2 或 i1 == i2 且 j1 < j2 。

示例 1 ：

输入：nums1 = [1,2,3,2,4], nums2 = [2,3,1,2,3]
输出：[0,3]
解释：取下标为 0 和下标为 3 的数对，计算出 |nums1[0]-nums1[3]| + |nums2[0]-nums2[3]| 的值为 1 ，这是我们能够得到的最小值。

示例 2 ：

输入：nums1 = [1,2,4,3,2,5], nums2 = [1,4,2,3,5,1]
输出：[1,4]
解释：取下标为 1 和下标为 4 的数对，计算出 |nums1[1]-nums1[4]| + |nums2[1]-nums2[4]| 的值为 1，这是我们可以达到的最小值。

提示：

2 <= nums1.length, nums2.length <= 10⁵
nums1.length == nums2.length
0 <= nums1_i<= nums1.length
0 <= nums2_i <= nums2.length

分析

平面最近点对-非分治算法

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


from sortedcontainers import SortedList
class Solution:
    def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        A = [(nums1[i],nums2[i],i) for i in range(n)]
        res = [inf,n,n]
        d = {}
        for a,b,i in A:
            if (a,b) in d:
                res = min(res,[0,d[(a,b)],i])
            d[(a,b)] = i
        if res[0]==0:
            return res[1:]
        A.sort()
        sl = SortedList()
        l = 0
        for x,y,j in A:
            mi = res[0]
            while x-A[l][0]>mi:
                x2,y2,i = A[l]
                sl.remove((y2,x2,i))
                l += 1
            a = sl.bisect_left((y-mi,))
            b = sl.bisect_left((y+mi+1,))
            for y2,x2,i in sl[a:b]:
                w = abs(x2-x)+abs(y2-y)
                res = min(res,[w]+sorted([i,j]))
            sl.add((y,x,j))
        return res[1:]

111 ms

目录

2613：美数对（★★）

题目

分析

解答