迭代时找到剩余数组中 2 个元素的最小差 python

Question

我正在遍历数组，每次我想找到与剩余数组差异最小的 2 个元素。例如给定 array=[5,3,6,1,3]，如果迭代器 i 位于索引 2，所以 array[i]=6，我想找到数组中除 6 之外的 2 个元素所能给出的最小差异。

我正在考虑为每次迭代寻找第一和第二最大元素，但我不知道如何忽略 array[i] 元素。任何提示将不胜感激。

Answer 1

在外循环中，使用 enumerate() 跟踪索引。然后在迭代其余项目（以获得最小差异）的内部循环上，还跟踪索引，以便我们可以在它等于外部循环的索引时跳过它。

这里有一些适合您的解决方案。我们不需要获得所有数字对的所有差异，因为这会导致阶乘时间复杂度（因为我们将获得所有可能的 combinations/pairs）。我们能做的就是简单地对数组进行排序，然后一旦排序

我们只需要得到每个连续数字的差，例如[1, 3, 10, 11, 12] 我们只需要减去 3 - 1、10 - 3、11 - 10 和 12 - 11。没有更多的意义去做例如12 - 1 因为我们确信它会大于任何连续的对。
除了连续的对，我们还需要交替对，这样如果我们删除一个数字，我们仍然会考虑它的前一个和下一个的区别，例如[10, 12, 14]。如果我们在第 12 项，则不应考虑 12 -10 和 14 - 12。但是 14 - 10 应该是！

解决方案 1

有点复杂，但时间复杂度只有O(n log n)。

对数组进行排序。排序后的值必须包含原始索引。
按排序顺序存储差异，但仅将其保持在最多 3 个项目中，其中这 3 个项目是最小的差异（与有界 min heaps 相同的想法）。
- 为什么是 3 项？比如说我们有 [1, 10, 12, 14, 100]。那么我们知道最小差是2，这是12 - 10和14 - 12的结果。对于项目 1，最小差异为 2，与项目 10、14 和 100 相同。但是对于 12，它不应该是 2，因为如果我们删除 12，下一个最小差异是 14 - 10，即 4。这将是最坏的情况。所以我们需要存储最多 3 个最小差异，这里是 12 - 10 中的 2 个，14 - 12 中的 2 个，以及 14 - 10 中的 4 个，这样我们就可以捕捉到 [=33] 的情况=] 应该选择第三个选项（4 来自 14 - 10）。
迭代原始数组。对于每个项目，查看第一个适用的差异并显示它。这将是不是在减法中使用当前项目的结果的差异。

from bisect import insort

numbers = [14, 10, -11, 27, 12, 4, 20]
numbers_sorted = sorted(enumerate(numbers), key=lambda value: value[1])  # O(n log n)

differences = []
for index in range(1, len(numbers_sorted)):  # O(n), the binary search and pop on <differences> are negligible because it is fixed at the constant size of 3
    for prev in range(1, 2 if index == 1 else 3):  # Subtract consecutive and alternating
        diff_tup = (
            numbers_sorted[index][1] - numbers_sorted[index-prev][1],
            numbers_sorted[index-prev],
            numbers_sorted[index],
        )
        insort(differences, diff_tup)
        if len(differences) > 3:
            differences.pop()

for index, num in enumerate(numbers):  # O(n), the iteration of <differences> is negligible because it is fixed at the constant size of 3
    for diff in differences:
        if index != diff[1][0] and index != diff[2][0]:
            print(f"{num}: min diff {diff[0]} from {diff[1][1]} and {diff[2][1]}")
            break

解决方案 2

更直接，但时间复杂度 O(n ^ 2)。

对数组进行排序。排序后的值必须包含原始索引。
在主循环中迭代数组。
- 对于每一项，迭代排序数组。
  - 如果项目是主循环中的项目，则跳过。
  - 否则，减去数字。
  - 如果小于当前最小值，则将其设置为新的最小值。
- 显示当前数字的最小值

from bisect import insort

numbers = [14, 10, -11, 27, 12, 4, 20]
numbers_sorted = sorted(enumerate(numbers), key=lambda value: value[1])  # O(n log n)

for num_index, num in enumerate(numbers):  # O(n ^ 2)
    min_diff = None
    min_subtractors = None
    
    for index in range(1, len(numbers_sorted)):
        for prev in range(1, 2 if index == 1 else 3):  # Subtract consecutive and alternating
            if num_index == numbers_sorted[index][0] or num_index == numbers_sorted[index-prev][0]:
                continue
            diff = numbers_sorted[index][1] - numbers_sorted[index-prev][1]
            if min_diff is None or diff < min_diff:
                min_diff = diff
                min_subtractors = (numbers_sorted[index-prev][1], numbers_sorted[index][1])

    print(f"{num}: min diff {min_diff} from {min_subtractors[0]} and {min_subtractors[1]}")

输出

14: min diff 2 from 10 and 12
10: min diff 2 from 12 and 14
-11: min diff 2 from 10 and 12
27: min diff 2 from 10 and 12
12: min diff 4 from 10 and 14
4: min diff 2 from 10 and 12
20: min diff 2 from 10 and 12

迭代时找到剩余数组中 2 个元素的最小差 python

Find the minimum difference of the 2 elements from the remaining array while iterating python

python

arrays

minimum

difference

解决方案 1

解决方案 2