2426-满足不等式的数对数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，两个数组的大小都为 n ，同时给你一个整数 diff
，统计满足以下条件的 **数对 **(i, j) ：

  • 0 <= i < j <= n - 1 且
  • nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff.

请你返回满足条件的 数对数目 。

示例 1：

**输入：** nums1 = [3,2,5], nums2 = [2,2,1], diff = 1
**输出：** 3
**解释：**
总共有 3 个满足条件的数对：
1. i = 0, j = 1：3 - 2 <= 2 - 2 + 1 。因为 i < j 且 1 <= 1 ，这个数对满足条件。
2. i = 0, j = 2：3 - 5 <= 2 - 1 + 1 。因为 i < j 且 -2 <= 2 ，这个数对满足条件。
3. i = 1, j = 2：2 - 5 <= 2 - 1 + 1 。因为 i < j 且 -3 <= 2 ，这个数对满足条件。
所以，我们返回 3 。

示例 2：

**输入：** nums1 = [3,-1], nums2 = [-2,2], diff = -1
**输出：** 0
**解释：**
没有满足条件的任何数对，所以我们返回 0 。

提示：

  • n == nums1.length == nums2.length
  • 2 <= n <= 105
  • -104 <= nums1[i], nums2[i] <= 104
  • -104 <= diff <= 104

视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

包含树状数组的原理，以及另外一种归并排序的做法。

树状数组/线段树逐渐成为周赛必备技能了。

本题用到的技巧是，合并下标相同的元素。

式子变形得

\textit{nums}_1[i]-\textit{nums}_2[i]\le\textit{nums}_1[j]-\textit{nums}_2[j]+\textit{diff}

记 a[i]=\textit{nums}_1[i]-\textit{nums}_2[i]，上式为

a[i]\le a[j]+\textit{diff}

因此本题和 剑指 Offer 51. 数组中的逆序对 、315. 计算右侧小于当前元素的个数 等题目实质上是同一类题，用归并排序或者树状数组等均可以通过。

下面代码用的离散化树状数组，即使元素范围达到 10^9 也适用。

[sol1-Python3]
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
class Solution:
    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:
        for i, x in enumerate(nums2):
            a[i] -= x
        b = sorted(set(a))  # 配合下面的二分，离散化

        ans = 0
        t = BIT(len(b) + 1)
        for x in a:
            ans += t.query(bisect_right(b, x + diff))
            t.add(bisect_left(b, x) + 1)
        return ans

class BIT:
    def __init__(self, n):
        self.tree = [0] * n

    def add(self, x):
        while x < len(self.tree):
            self.tree[x] += 1
            x += x & -x

    def query(self, x):
        res = 0
        while x > 0:
            res += self.tree[x]
            x &= x - 1
        return res
[sol1-Java]
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public long numberOfPairs(int[] a, int[] nums2, int diff) {
        var n = a.length;
        for (var i = 0; i < n; ++i)
            a[i] -= nums2[i];
        var b = Arrays.stream(a).distinct().sorted().toArray(); // 配合下面的二分，离散化

        var ans = 0L;
        var t = new BIT(b.length + 1);
        for (var x : a) {
            ans += t.query(lowerBound(b, x + diff + 1));
            t.add(lowerBound(b, x) + 1);
        }
        return ans;
    }

    private int lowerBound(int[] a, int x) {
        int left = 0, right = a.length;
        while (left < right) {
            var mid = left + (right - left) / 2;
            if (a[mid] < x) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

class BIT {
    private final int[] tree;

    public BIT(int n) {
        tree = new int[n];
    }

    public void add(int x) {
        while (x < tree.length) {
            ++tree[x];
            x += x & -x;
        }
    }

    public int query(int x) {
        var res = 0;
        while (x > 0) {
            res += tree[x];
            x &= x - 1;
        }
        return res;
    }
}
[sol1-C++]
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class BIT {
private:
    vector<int> tree;

public:
    BIT(int n) : tree(n) {}

    void add(int x) {
        while (x < tree.size()) {
            ++tree[x];
            x += x & -x;
        }
    }

    int query(int x) {
        int res = 0;
        while (x > 0) {
            res += tree[x];
            x &= x - 1;
        }
        return res;
    }
};

class Solution {
public:
    long long numberOfPairs(vector<int> &a, vector<int> &nums2, int diff) {
        int n = a.size();
        for (int i = 0; i < n; ++i)
            a[i] -= nums2[i];
        auto b = a;
        sort(b.begin(), b.end());
        b.erase(unique(b.begin(), b.end()), b.end()); // 配合下面的二分，离散化

        long ans = 0L;
        auto t = new BIT(n + 1);
        for (int x : a) {
            ans += t->query(upper_bound(b.begin(), b.end(), x + diff) - b.begin());
            t->add(lower_bound(b.begin(), b.end(), x) - b.begin() + 1);
        }
        return ans;
    }
};
[sol1-Go]
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
30
31
32
33
34
35
36
37
38
39
func numberOfPairs(a, nums2 []int, diff int) (ans int64) {
	for i, x := range nums2 {
		a[i] -= x
	}
	// 配合下面的二分，离散化
	set := map[int]struct{}{}
	for _, v := range a {
		set[v] = struct{}{}
	}
	b := make(sort.IntSlice, 0, len(set))
	for x := range set {
		b = append(b, x)
	}
	sort.Ints(b)

	t := make(BIT, len(a)+1)
	for _, x := range a {
		ans += int64(t.query(b.Search(x + diff + 1)))
		t.add(b.Search(x) + 1)
	}
	return
}

type BIT []int

func (t BIT) add(x int) {
	for x < len(t) {
		t[x]++
		x += x & -x
	}
}

func (t BIT) query(x int) (res int) {
	for x > 0 {
		res += t[x]
		x &= x - 1
	}
	return
}

复杂度分析

  • 时间复杂度：O(n\log n)，其中 n 为 nums}_1 的长度。
  • 空间复杂度：O(n)。
 Comments
On this page
2426-满足不等式的数对数目