0

这是一个特定于任务的代码，我想知道是否有更好的方法。因此，喜欢逻辑和编码的人，请帮助我。

这是问题：

令 A 为 n 个正整数的数组。所有元素都是不同的。如果 A[i] > A[j] 并且 i < j 则对 (i, j) 称为 A 的特殊对。给定 n 求 A 的特殊对的数量。

它非常简单直接。这是我实施的以下解决方案。逻辑部分。

         for(int j=0;j<nos.size();j++)
            {
                    for(int k=j+1;k<nos.size();k++)//always maintain condition that i<j and simply compare the numbers.
                    {
                            if(nos[j] > nos[k])
                            {
                                    spc++;//compute special pair.
                            }
                    }
            }

每个 nos[i] 都包含要计算特殊对的数组。有没有办法使用单个循环来做到这一点？或任何其他可以节省时间且速度更快的逻辑。在此先感谢我寻求从中了解更多信息。

你能告诉我如何在不执行代码的情况下确定哪个代码更快。非常欢迎您的意见。

主要问题是计算特殊对的数量。因此，只是 spc 的增量。

4

3 回答 3

3

我认为@syam 是正确的，这可以在 O(N log N) 时间（和 O(N) 额外空间）内完成。

您可以使用平衡二叉树来做到这一点，其中每个节点不仅有一个值，而且还有其左子树中后代数量的计数。

要计算特殊对，您需要将数组从末尾遍历到开头，然后将每个项目插入树中。当您在树中插入项目时，您会在其左侧子树中找到项目的数量——那些是小于它但在数组中位于其右侧的项目（即，每个代表一个特殊的对）。由于我们只通过 ~log(N) 节点向下插入一个项目，因此计算左侧项目数的时间也是 O(log N)。我们还必须将左侧项目的计数更新大约 log(N)/2 次（再次，对数复杂度）。

这给了 O(N log N) 时间。

编辑以获取更多详细信息：树的平衡是相当传统的（例如，AVL-或 RB-tree），增加了在旋转时向左调整项目数以恢复平衡。

当您插入每个项目时，您会通过树向下到达将要插入的点。在根节点，您只需记录左子树中的项目数。然后假设你的新项目大于那个，所以你向右下降。当你这样做时，你正在做两件事：记录你的当前位置，这样你就知道这个节点相对于已经插入的节点的位置，并更新树中的计数，这样你就可以为以后的插入获得准确的计数.

所以，让我们通过一个小样本来研究。为了论证，假设我们的输入是 [6, 12, 5, 9, 7]。所以，我们的第一个插入是 7，它成为我们树的根，没有后代，并且（显然）在它的左边是 0。

然后我们在它的右边插入 9。因为它在右边，所以我们不需要在下降过程中调整任何计数——我们只需将我们的项目计数增加到左边。就是这样，所以我们知道 9 我们有一对特殊的对（[9,7]，尽管我们没有跟踪它）。

然后我们插入 5。这是 7 的左侧，所以当我们从 7 下降时，我们将其左侧的项目计数增加到 1。我们插入 5，左侧没有项目，所以它的计数为 0 ，并且没有特殊的对。

然后我们插入 12。当我们点击根节点 (7) 时，它左侧的计数为 1。我们向右下降，所以我们再次为根节点本身增加。然后我们从 9 再次向右下降，所以我们再添加一个（从它的左子树 +0），所以 12 有三个特殊对。

然后我们插入 6。我们从 7 向左下降，所以我们不添加任何东西。我们从 5 向右下降，所以我们添加 1（同样，从它的左子树 +0）。所以它有一对特殊的。

即使您需要生成所有特殊对（不仅仅是计算它们），您也可以期望树在平均情况下提高速度（即，除了按降序排序之外的几乎任何东西）。为了生成所有特殊对，我们像以前一样将每个项目插入树中，然后遍历该项目左侧的树。朴素算法遍历（并比较）数组右侧的所有元素以找到那些可能是特殊对的元素，而这只需要遍历树以找到那些实际上是特殊对的元素。

不过，这确实有一个副作用：它以不同的顺序生成对。每对不是按照它在数组中出现的顺序生成的，而是按第二个元素的降序生成。例如，给定一个像 [4,1,2,3] 这样的输入，朴素算法会产生 [[4,1], [4,2], [4,3]]，但这会产生 `[[4 ,3]、[4,2]、[4,1]]。

于 2013-09-28T21:24:30.290 回答
2

你的意思是你能比二次运行时做得更好吗？不。要看到这一点，请考虑递减序列A = (N, N - 1, ..., 2, 1)。对于这个序列，所有的对(i, j)都是i < j特殊的，并且有O(N^2)这样的对。由于您必须输出每个特殊对，因此您需要二次时间来执行此操作。

于 2013-09-28T20:15:46.747 回答
1

我不认为你可以改进你的算法。在我看来，它显示了 O(n²) 的复杂性。您可以通过计算程序必须为长度为 n 的数组执行的内部循环数来证明这一点。第一个循环将有 n-1 次迭代，第二个循环 n-2，第三个 n-3 等等。使用前 n 个整数之和的公式进行总结（这次只是向后，不是从 1 到 n，而是从 2 到 n-1）：

(n-1)+(n-2)+(n-3)+...3+2 = n*(n-1)/2 - 1. 您不必遍历最后一个剩余元素，因为没有其他元素可供比较。实际上，这是我对您的算法看到的唯一改进；-)：

for(int j=0;j<nos.size();j++)

至

for(int j=0;j<nos.size()-1;j++)

总结大 n 表达式 n*(n-1)/2 - 1 的行为类似于 n²，这就是我相信 O(n²) 的来源。如果我错了，请纠正我。

于 2013-09-28T21:12:44.747 回答