feat: add problem $2817

azl397985856 · web-flow · commit 420ffb98d197 · 2023-08-20T11:47:33.000+08:00
diff --git a/problems/2817.minimum-absolute-difference-between-elements-with-constraint.md b/problems/2817.minimum-absolute-difference-between-elements-with-constraint.md
@@ -0,0 +1,147 @@
+## 题目地址(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`。这意味着在最坏的情况下数组中的元素值可能非常大，从而导致内层循环的迭代次数也将会巨大，最后可能会出现执行超时的问题。
+
+下面是尝试暴力解法的代码：
+```python
+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` 中的前一个元素）的差值更新结果 `res`，`res` 的值为当前 `res` 和新的差值中的较小值。
+6. 如果 `idx` 小于 `ls` 的长度（即 `nums[i + x]` 在 `ls` 中的后一个元素存在），则尝试使用 `nums[i + x]` 和 `ls[idx]` 的差值更新结果 `res`。
+7. 循环结束后，返回结果 `res`，这是数组中所有相隔 `x` 的元素的最小绝对差。
+
+
+## 代码
+
+- 语言支持：Python3
+
+Python3 Code:
+
+```python
+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)，大大提高了算法的执行效率。
