class Solution {
public:
vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
}
};
1906. 查询差绝对值的最小值
一个数组 a 的 差绝对值的最小值 定义为：0 <= i < j < a.length 且 a[i] != a[j] 的 |a[i] - a[j]| 的 最小值。如果 a 中所有元素都 相同 ，那么差绝对值的最小值为 -1 。
[5,2,3,7,2] 差绝对值的最小值是 |2 - 3| = 1 。注意答案不为 0 ，因为 a[i] 和 a[j] 必须不相等。给你一个整数数组 nums 和查询数组 queries ，其中 queries[i] = [li, ri] 。对于每个查询 i ，计算 子数组 nums[li...ri] 中 差绝对值的最小值 ，子数组 nums[li...ri] 包含 nums 数组（下标从 0 开始）中下标在 li 和 ri 之间的所有元素（包含 li 和 ri 在内）。
请你返回 ans 数组，其中 ans[i] 是第 i 个查询的答案。
子数组 是一个数组中连续的一段元素。
|x| 的值定义为：
x >= 0 ，那么值为 x 。x < 0 ，那么值为 -x 。
示例 1：
输入：nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]] 输出：[2,1,4,1] 解释：查询结果如下： - queries[0] = [0,1]：子数组是 [1,3] ，差绝对值的最小值为 |1-3| = 2 。 - queries[1] = [1,2]：子数组是 [3,4] ，差绝对值的最小值为 |3-4| = 1 。 - queries[2] = [2,3]：子数组是 [4,8] ，差绝对值的最小值为 |4-8| = 4 。 - queries[3] = [0,3]：子数组是 [1,3,4,8] ，差的绝对值的最小值为 |3-4| = 1 。
示例 2：
输入：nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]] 输出：[-1,1,1,3] 解释：查询结果如下： - queries[0] = [2,3]：子数组是 [2,2] ，差绝对值的最小值为 -1 ，因为所有元素相等。 - queries[1] = [0,2]：子数组是 [4,5,2] ，差绝对值的最小值为 |4-5| = 1 。 - queries[2] = [0,5]：子数组是 [4,5,2,2,7,10] ，差绝对值的最小值为 |4-5| = 1 。 - queries[3] = [3,5]：子数组是 [2,7,10] ，差绝对值的最小值为 |7-10| = 3 。
提示：
2 <= nums.length <= 1051 <= nums[i] <= 1001 <= queries.length <= 2 * 1040 <= li < ri < nums.length原站题解
python3 解法, 执行用时: 4180 ms, 内存消耗: 27.5 MB, 提交时间: 2023-06-07 11:01:51
class Solution:
def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
# 将每个数字对应的下标存入哈希表
dic=collections.defaultdict(list)
for i,num in enumerate(nums):
dic[num].append(i)
res=[-1]*len(queries)
# 查询
for i,(l,r) in enumerate(queries):
pre=-inf
minv=inf
# 遍历1~100中的数字是否存在于区间[l,r]中，相邻数之差最小
for j in range(1,101):
a=bisect.bisect_left(dic[j],l)
b=bisect.bisect_right(dic[j],r)-1
if a<=b:
minv=min(minv,j-pre)
pre=j
# 区间内没有不相同的数据
if minv!=inf:
res[i]=minv
return res
python3 解法, 执行用时: 2476 ms, 内存消耗: 109.8 MB, 提交时间: 2023-06-07 11:01:24
class Solution:
def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
# 元素 c 的最大值
C = 100
n = len(nums)
# 前缀和
pre = [[0] * (C + 1)]
for i, num in enumerate(nums):
pre.append(pre[-1][:])
pre[-1][num] += 1
ans = list()
for left, right in queries:
# last 记录上一个出现的元素
# best 记录相邻两个元素差值的最小值
last = 0
best = float("inf")
for j in range(1, C + 1):
if pre[left][j] != pre[right + 1][j]:
if last != 0:
best = min(best, j - last)
last = j
if best == float("inf"):
best = -1
ans.append(best)
return ans
cpp 解法, 执行用时: 1276 ms, 内存消耗: 84.9 MB, 提交时间: 2023-06-07 11:01:06
class Solution {
public:
vector<int> minDifference(vector<int> &nums, vector<vector<int>> &queries) {
int n = nums.size(), nq = queries.size();
vector<int> ans(nq);
vector<vector<int>> pos(101); // pos[v] 为 v 在数组 nums 中的所有出现位置
for (int i = 0; i < n; ++i) {
pos[nums[i]].push_back(i);
}
for (int i = 0; i < nq; ++i) {
auto &q = queries[i];
int l = q[0], r = q[1] + 1; // 左闭右开
int minDiff = 1e9, pre = -1e9;
for (int v = 1; v <= 100; ++v) {
auto &ps = pos[v];
if (ps.empty()) {
continue;
}
// 二分查询 [l,r) 区间内有多少个 v
int cnt = lower_bound(ps.begin(), ps.end(), r) - lower_bound(ps.begin(), ps.end(), l);
if (cnt == r - l) { // [l,r) 内所有元素都是 v
minDiff = -1;
break;
}
if (cnt > 0) { // [l,r) 内含有 v
minDiff = min(minDiff, v - pre);
pre = v;
}
}
ans[i] = minDiff;
}
return ans;
}
};
golang 解法, 执行用时: 592 ms, 内存消耗: 10.4 MB, 提交时间: 2023-06-07 11:00:52
// 二分元素位置
func minDifference(a []int, qs [][]int) []int {
ans := make([]int, len(qs))
pos := make([]sort.IntSlice, 101)
for i, v := range a {
pos[v] = append(pos[v], i)
}
outer:
for i, q := range qs {
l, r, d, pre := q[0], q[1]+1, int(1e9), int(-1e9)
for v, ps := range pos {
if ps == nil {
continue
}
cnt := ps[ps.Search(l):].Search(r) // 二分查询 v 的个数
if cnt == r-l { // 所有元素都相同
ans[i] = -1
continue outer
}
if cnt > 0 { // 子数组包含元素 v
if v-pre < d {
d = v - pre
}
pre = v
}
}
ans[i] = d
}
return ans
}
golang 解法, 执行用时: 220 ms, 内存消耗: 188.4 MB, 提交时间: 2023-06-07 11:00:35
// 个数前缀和
func minDifference(a []int, qs [][]int) []int {
sum := make([][101]int, len(a)+1)
for i, v := range a {
sum[i+1] = sum[i]
sum[i+1][v]++
}
ans := make([]int, len(qs))
outer:
for i, q := range qs {
l, r, d, pre := q[0], q[1]+1, int(1e9), int(-1e9)
for v := 1; v <= 100; v++ {
cnt := sum[r][v] - sum[l][v] // v 的个数
if cnt == r-l { // 所有元素都相同
ans[i] = -1
continue outer
}
if cnt > 0 { // 子数组包含元素 v
if v-pre < d {
d = v - pre
}
pre = v
}
}
ans[i] = d
}
return ans
}