3520. 逆序对计数的最小阈值 🔒

题目描述

给定一个整数数组 nums 和一个整数 k。

阈值 为 x 的逆序对是一对下标 (i, j) 满足：

• i < j
• nums[i] > nums[j]
• 两个数字的差 最多为 x（即 nums[i] - nums[j] <= x）。

你的任务是确定最小的整数 min_threshold，使得 至少 有 k 个逆序对的阈值是 min_threshold。

如果没有这样的整数，返回 -1。

 

示例 1：

输入：nums = [1,2,3,4,3,2,1], k = 7

输出：2

解释：

对于阈值 x = 2，逆序对有：

1. (3, 4) 其中 nums[3] == 4 和 nums[4] == 3.
2. (2, 5) 其中 nums[2] == 3 和 nums[5] == 2.
3. (3, 5) 其中 nums[3] == 4 和 nums[5] == 2.
4. (4, 5) 其中 nums[4] == 3 和 nums[5] == 2.
5. (1, 6) 其中 nums[1] == 2 和 nums[6] == 1.
6. (2, 6) 其中 nums[2] == 3 和 nums[6] == 1.
7. (4, 6) 其中 nums[4] == 3 和 nums[6] == 1.
8. (5, 6) 其中 nums[5] == 2 和 nums[6] == 1.

如果我们选择小于 2 的任意整数作为阈值，则逆序对的数量少于 k。

示例 2：

输入：nums = [10,9,9,9,1], k = 4

输出：8

解释：

对于阈值 x = 8，逆序对有：

1. (0, 1) 其中 nums[0] == 10 和 nums[1] == 9。
2. (0, 2) 其中 nums[0] == 10 和 nums[2] == 9。
3. (0, 3) 其中 nums[0] == 10 和 nums[3] == 9。
4. (1, 4) 其中 nums[1] == 9 和 nums[4] == 1。
5. (2, 4) 其中 nums[2] == 9 和 nums[4] == 1。
6. (3, 4) 其中 nums[3] == 9 和 nums[4] == 1。

如果我们选择小于 8 的任意整数作为阈值，则逆序对的数量少于 k。

 

提示：

• 1 <= nums.length <= 104
• 1 <= nums[i] <= 109
• 1 <= k <= 109

解法

方法一

Python3JavaC++Go

评论