Select 对数字总差最小
Select pairs of numbers with the minimum overall difference
给定n对数，selectk对使得最小值与最大值之差是最小的。请注意，一对中的 2 个数字不能分开。示例 (n=5, k=3):
INPUT OUTPUT (return the index of the pairs)
5 4 1 2 4
1 5
9 8
1 0
2 7
在这种情况下，选择 (5,4) (1,5) (1,0) 将得到 5 （最大值为 5 , 最小值为 0)。我正在寻找一种有效的方法 (n log n) 来执行此操作，因为输入会非常大，我不想遍历所有可能的情况。
谢谢。
注意：不需要代码。解决方案的解释就足够了。
让我们继续排序数组：一个根据成对的最小数量排序，另一个根据最大数量排序。让我们遍历第一个数组并修复答案中的最小数字。我们可以将指针指向第二个数组中的第 k 个数字。当我们转到下一对时，如果需要，我们会从第二个数组和前向指针中删除所有最小值较小的对。要在第二个数组中找到 log n 时间的位置，我们可以在对和位置之间保留额外的映射。
这是一个时间复杂度为 O(n log n) 的方法：
首先根据对中较小的数字对数组进行排序。现在从排序数组中的最后一个元素（具有最高最小值的对）开始迭代。
随着我们向后移动，已经访问过的元素的最小值必然等于或高于当前元素。根据访问对中的maximal个数，将访问对存储在最大堆中。如果堆大小小于 k-1，则继续添加到堆中。
一旦堆大小等于k-1，开始记录和比较迄今为止的最佳间隔。如果堆大小超过 k-1，弹出最大元素。堆保证包含第一个 k-1 对，其中最小数大于或等于当前最小数，最大数最小（因为当堆大小超过 [=12 时我们不断弹出最大元素=]).
排序的总时间 O(n log n) + 迭代和维护堆的 O(n log n) = 总共 O(n log n)。
示例：
5 4
1 5
9 8
1 0
2 7
k = 3
Sort pairs by the smaller number in each pair:
[(1,0),(1,5),(2,7),(5,4),(9,8)]
Iterate from end to start:
i = 4; Insert (9,8) into heap
i = 3; Insert (5,4) into heap
i = 2; Range = 2-9
i = 1; Pop (9,8) from heap; Range = 1-7
i = 0; Pop (2,7) from heap; Range = 0-5
Minimal interval [0,5] (find k matching indices in O(n) time)
给定n对数，selectk对使得最小值与最大值之差是最小的。请注意，一对中的 2 个数字不能分开。示例 (n=5, k=3):
INPUT OUTPUT (return the index of the pairs)
5 4 1 2 4
1 5
9 8
1 0
2 7
在这种情况下，选择 (5,4) (1,5) (1,0) 将得到 5 （最大值为 5 , 最小值为 0)。我正在寻找一种有效的方法 (n log n) 来执行此操作，因为输入会非常大，我不想遍历所有可能的情况。
谢谢。
注意：不需要代码。解决方案的解释就足够了。
让我们继续排序数组：一个根据成对的最小数量排序，另一个根据最大数量排序。让我们遍历第一个数组并修复答案中的最小数字。我们可以将指针指向第二个数组中的第 k 个数字。当我们转到下一对时，如果需要，我们会从第二个数组和前向指针中删除所有最小值较小的对。要在第二个数组中找到 log n 时间的位置，我们可以在对和位置之间保留额外的映射。
这是一个时间复杂度为 O(n log n) 的方法：
首先根据对中较小的数字对数组进行排序。现在从排序数组中的最后一个元素（具有最高最小值的对）开始迭代。
随着我们向后移动，已经访问过的元素的最小值必然等于或高于当前元素。根据访问对中的maximal个数，将访问对存储在最大堆中。如果堆大小小于 k-1，则继续添加到堆中。
一旦堆大小等于k-1，开始记录和比较迄今为止的最佳间隔。如果堆大小超过 k-1，弹出最大元素。堆保证包含第一个 k-1 对，其中最小数大于或等于当前最小数，最大数最小（因为当堆大小超过 [=12 时我们不断弹出最大元素=]).
排序的总时间 O(n log n) + 迭代和维护堆的 O(n log n) = 总共 O(n log n)。
示例：
5 4
1 5
9 8
1 0
2 7
k = 3
Sort pairs by the smaller number in each pair:
[(1,0),(1,5),(2,7),(5,4),(9,8)]
Iterate from end to start:
i = 4; Insert (9,8) into heap
i = 3; Insert (5,4) into heap
i = 2; Range = 2-9
i = 1; Pop (9,8) from heap; Range = 1-7
i = 0; Pop (2,7) from heap; Range = 0-5
Minimal interval [0,5] (find k matching indices in O(n) time)