Skip to content

Latest commit

 

History

History
147 lines (96 loc) · 5.98 KB

2817.minimum-absolute-difference-between-elements-with-constraint.md

File metadata and controls

147 lines (96 loc) · 5.98 KB

题目地址(2817. 限制条件下元素之间的最小绝对差)

https://leetcode.cn/problems/minimum-absolute-difference-between-elements-with-constraint

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 x 。

请你找到数组中下标距离至少为 x 的两个元素的 差值绝对值 的 最小值 。

换言之,请你找到两个下标 i 和 j ,满足 abs(i - j) >= x 且 abs(nums[i] - nums[j]) 的值最小。

请你返回一个整数,表示下标距离至少为 x 的两个元素之间的差值绝对值的 最小值 。

 

示例 1:

输入:nums = [4,3,2,4], x = 2
输出:0
解释:我们选择 nums[0] = 4 和 nums[3] = 4 。
它们下标距离满足至少为 2 ,差值绝对值为最小值 0 。
0 是最优解。
示例 2:

输入:nums = [5,3,2,10,15], x = 1
输出:1
解释:我们选择 nums[1] = 3 和 nums[2] = 2 。
它们下标距离满足至少为 1 ,差值绝对值为最小值 1 。
1 是最优解。
示例 3:

输入:nums = [1,2,3,4], x = 3
输出:3
解释:我们选择 nums[0] = 1 和 nums[3] = 4 。
它们下标距离满足至少为 3 ,差值绝对值为最小值 3 。
3 是最优解。
 

提示:

1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= x < nums.length

前置知识

  • 二分查找

思路

初始思考与暴力解法

在这个题目里,我首先考虑到的是最简单的方式,也就是暴力破解的方式。这种方法的时间复杂度为O(n^2),但是在题目的提示中还给出了数据范围为1 <= nums[i] <= 10^9。这意味着在最坏的情况下数组中的元素值可能非常大,从而导致内层循环的迭代次数也将会巨大,最后可能会出现执行超时的问题。

下面是尝试暴力解法的代码:

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        n = len(nums)
        minDiff = float('inf')

        for i in range(n):
            for j in range(i + x, n):
                absDiff = abs(nums[i] - nums[j])
                if absDiff < minDiff:
                    minDiff = absDiff

        return minDiff

寻求更高效的解决方案

在面对大规模数据或数据范围较大的情况下,我们需要寻找更高效的算法来解决这个题目,以避免超时的问题。为了降低复杂度,我们可以通过维护一个有序集合,并使用二分查找的方式进行更快的插入和查找操作,从而减少迭代次数。

在这个问题中,我们使用二分查找的思路进行优化主要有两个目的:

  1. 快速插入:由于我们需要维护一个有序数组,每次插入一个新元素时,如果使用普通的插入方式,可能需要遍历整个数组才能找到插入位置,时间复杂度为O(n)。但是,如果使用二分查找,我们可以在对数时间内找到插入位置,时间复杂度为O(log n)。
  2. 快速查找:对于每个索引为 i + x 的元素,我们需要在有序数组中找出最接近它的元素。如果使用普通的查找方式,可能需要遍历整个数组才能找到该元素,时间复杂度为O(n)。但是,如果使用二分查找,我们可以在对数时间内找到该元素,时间复杂度为O(log n)。

这种优化策略可以将算法的复杂度从O(n^2)降为O(N log N)。

优化策略的具体实现

  1. 初始化:定义一个变量 res 为无穷大,用于存储最小的绝对差。同时定义一个 SortedList 对象 ls ,用于存储遍历过的元素并保持其有序性。
  2. 遍历数组:使用 for 循环遍历 nums 数组。
  3. 每次循环中,先获取当前元素 nums[i],然后将其添加到有序列表 ls 中。
  4. 获取 nums[i + x],然后使用 SortedList.bisect_right 方法在有序列表 ls 中找到最后一个不大于 nums[i+x] 的元素的位置 idx
  5. 使用 nums[i + x] 和 ls[idx - 1](即 nums[i + x] 在 ls 中的前一个元素)的差值更新结果 resres 的值为当前 res 和新的差值中的较小值。
  6. 如果 idx 小于 ls 的长度(即 nums[i + x] 在 ls 中的后一个元素存在),则尝试使用 nums[i + x] 和 ls[idx] 的差值更新结果 res
  7. 循环结束后,返回结果 res,这是数组中所有相隔 x 的元素的最小绝对差。

代码

  • 语言支持:Python3

Python3 Code:

from sortedcontainers import SortedList

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        n = len(nums)

        # 初始化答案为无穷大
        res = float('inf')  

        # 维护前面元素的有序序列
        ls = SortedList()  

        for i in range(n - x):

            # 将nums[i]加入有序序列ls,SortedList保证插入后仍然有序
            v = nums[i]
            ls.add(v) 

            # 使用二分查找寻找前面序列中最后一个<=nums[i+x]的元素
            v = nums[i + x]
            idx = ls.bisect_right(v)

            # 使用和nums[i+x]最接近的元素更新答案,将答案更新为当前答案和新差值中的较小值
            res = min(res, abs(v - ls[idx - 1]))

            # 如果存在更接近的元素,也尝试更新答案
            if idx < len(ls):  
                res = min(res, abs(ls[idx] - v))

        return res

复杂度分析

令 n 为数组长度

  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:$O(n)$

我们的主要循环是 for i in range(n - x),这个循环会执行大约 n 次。在这个循环中,有两个关键操作会影响时间复杂度: ls.add(v)ls.bisect_right(v)

ls.add(v) 是一个向 SortedList 添加元素的操作,其时间复杂度为 O(log n)。ls.bisect_right(v) 是二分查找,其时间复杂度也为 O(log n)。

因此,整个循环的时间复杂度为 O(n) * O(log n) = O(n log n)。这样,我们成功地将原本暴力破解中 O(n^2) 的复杂度优化为了 O(n log n),大大提高了算法的执行效率。