算法：从未知数组中查找第二小的元素的索引

Question

我已经思考我的家庭作业问题有一段时间了。我欢迎（并且更喜欢）任何有关如何解决此问题的建议或方法。

基本上，我有一个大小为 N 的数组 A。我们不知道元素，但我们知道它们是不同的。我唯一拥有的是一个会在 N 中取两个索引 (i,j) 的人。然后这个人会告诉我 A[j] 是否 <<或>人工智能]。我想通过向此人询问 <= n + log n 问题来找到查找第二小元素索引的算法。

Answer 1

这个答案描述了如何找到第二大元素；可以类似地找到第二小的值。为简单起见，我们还假设所有数字都不同。

为了找到最大的元素，让我们构建一棵“冠军”树：将元素配对，决定哪个更大（那个是“获胜者”），然后将获胜者配对，决定哪个更大，依此类推，直到你找到“冠军”，这是最伟大的元素。这需要n步。现在，第二大要素肯定是与冠军相比。 （因为只有冠军才能击败它）。 log n 个元素已与冠军进行了比较，因此从这些元素中选择最大的；这需要 log n 步。

作为示例，让我们看看这对于数字元组 [6,4,3,5,2,1] 是如何工作的。在第一轮中，对是(6,4)、(3,5)、(2,1)。获胜者是每对中较大的元素，即 6、5、2。第二轮对是(6,5), 2。（这里2没有对，所以会自动晋级下一轮）。第二轮的获胜者是 6 和 2，第三轮的获胜者是 (6,2)，6 获胜。现在，通过配对元素并选择获胜者，我们构建了一个（有根的二叉）树：

这棵树具有以下属性：对于节点 x 及其子节点 y,z，我们有 x>=y, x>=z，因此
我们知道最大的元素是顶部（根部）的元素。我们还知道第二大元素 w 没有到达顶部，因此它在树中有一个父元素。但它的父元素大于或等于 w，因此在树的某个级别，最大元素的子元素之一是 w。 （换句话说，第二大元素只能被最大元素‘击败’）。因此，我们所要做的就是返回最大元素所采取的路径并收集所有直接子元素，我们知道第二大元素就在其中。在我们的例子中，这些是元素 2,5,4 。 （一般来说，大约有 log n 个，其中 log 表示以 2 为底的对数，因为树的高度约为 log n。） 。从这些元素中，我们使用任何需要 log n 步的方法选择最大的元素，然后我们找到了第二大的元素。

所有这些可能会让我们想起冠军，其中数字表示每支球队的“优秀”程度，因此有“冠军树”一词。

Answer 2

首先，找到最小的元素。您可以通过 n-1 次比较来实现此目的，即每个元素最多与 log(n) 个其他元素进行比较。现在查看哪些元素与最小元素进行了比较，并找到其中最小的元素。

Answer 3

unknown array = a[].
min1 = a[0].              first element.
min2 = 0.                 can equal anything

for(start at 0, until the end, grow by one):
    if(min1 > a[n]):
      min2 = min1.
      min1 = a[n].

return min2.

Answer 4

传奇

S 空间复杂度
T 时间复杂度

我是 Arnab Dutta。我有一个发言权...为什么不选择：

1. maintain the elements as a MIN-HEAP array
                       [S = 0, 
                        T = O(n) if optimized <- ignore as its 1 time activity]
2. call deleteMin() 2 times 
                       [T <= h(tree_height) 
                                   - as internally deleteMin() calls shiftDown()]

所以总 T = O(h)

任何人都可以解释为什么这不比使用

     a. Tournament or
     b. using MAX-HEAP

“注意：步骤 1”更好，可以就空间和时间复杂性进行争论。

Answer 5

研究排序算法，例如合并排序，其最坏情况复杂度为 O(n log n)。 “人”告诉你是否 A[j] > A[i] true or false 显然是一个比较函数。

合并排序的工作原理是将数组递归地分成两个较小的数组，其大小是原始数组的一半，然后再次对这些数组应用合并排序算法。如果您到达只有一个元素的两个数组的最后一步，您可以要求 person/comparison 函数告诉您如何对这些数组/元素进行排序。从这一步开始，您开始将子数组合并回原来的、但现在已排序的数组。

最后，您可以简单地返回排序数组的第二个元素，这是第二小的元素。

Answer 6

解决此类问题的最佳方法通常是“分而治之”。即尝试简化/划分问题，解决更简单的问题，然后看看它是否提供了任何有助于您解决原始问题的见解。如果更简单的问题仍然太难，请尝试进一步简化，等等。

在这种情况下，您可以从从数组中查找最小元素开始。你会怎么做？

Answer 7

1. 使用 2 个变量 - varSmallest 和 var2ndSmallest
2. 要求人员比较数组中的第一个和第二个值 - 将较小的索引设置为 varSmallest，将另一个设置为 var2ndSmallest
3. 按顺序获取下一个索引并将其命名为 varIndexToCheck
4. 比较 varIndexToCheck 和 var2ndSmallest 的值 - if value varIndexToCheck 的值大于 var2ndSmallest 的值，转至步骤 3
5. 比较 varIndexToCheck 和 varSmallest 的值 - 如果 varIndexToCheck 的值大于 varSmallest 的值，则设置 var2ndSmallest = varIndexToCheck 并转至步骤 3
6. 否则，设置 var2ndSmallest = varSmallest 和 varSmallest = varIndexToCheck 和然后转到步骤3

重复直到没有更多索引。之后，结果索引位于 var2ndSmallest 变量内，复杂度为 O(n log n)