c++ - 使用单个循环而不是 2 个 c++` 完成任务

Question

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

这是问题:

令 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 的增量。

Answer 1

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

您可以使用平衡二叉树执行此操作，其中每个节点不仅有一个值，而且还有其左子树中后代数量的计数。

要对特殊对进行计数，您需要从头到尾遍历数组，然后将每一项插入树中。当您将项目插入树中时，您会发现其左子树中项目的数量——那些比它少但在数组右侧的项目(即，每个代表一个特殊的对).由于我们只下降到 ~log(N) 个节点以插入一个项目，因此计算左侧项目数的时间也是 O(log N)。我们还必须将左侧的项目计数更新大约 log(N)/2 次(同样，对数复杂度)。

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

编辑更多细节:树的平衡是相当传统的(例如，AVL 树或 RB 树)，并在旋转以恢复平衡时向左调整项目的数量。

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

那么，让我们研究一个小样本。为了论证，我们假设我们的输入是 [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)。所以它有一对特殊的。

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

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