证明我的算法是正确的，在合理范围内

我正在研究一些算法分配，并被问到以下问题:在O(n)中对元素'r'或'w'进行排序，因此'r'总是在'w'之前。因此，如果输入看起来像[w,r,w,r,w,r,w,w]，在算法运行后，数组看起来像[r,r,r,w,w,w,w]。

从概念上讲，这似乎非常清楚。我必须使用两个边界变量来保存第一个"w"元素的位置，另一个保存最后一个"r"元素的位置。

我的代码如下:

char[] A = new char[] { 'w', 'r', 'w', 'r', 'w', 'r', 'w', 'w' };
int lastRedPosition = A.Length - 1;
int firstWhitePosition = 0;
for (int i = firstWhitePosition ; i < A.Length; i++)
{
    // determine the first red from the right e.g. the lastred, ending at the firstwhite position
    for (int j = lastRedPosition; j > firstWhitePosition; j--)
    {
        if (A[j] == 'r')
        {
            lastRedPosition = j;
            break;
        }
    }
    for (int k = firstWhitePosition; k < lastRedPosition; k++)
    {
        if (A[k] == 'w')
        {
            firstWhitePosition = k;
            break;
        }
    }
    A[firstWhitePosition] = 'r';
    A[lastRedPosition] = 'w';
}

现在我认为它运行在O(n)，直观地说，尽管有嵌套的for循环。这是因为，总而言之，数组只被遍历一次。因为我们用lastRedPosition和firstWhitePosition变量记录了我们的位置

然而，我发现很难更正式地激发这一点，因为同样嵌套的for循环…有人能给我指点一下正确的方向吗?

这不是快速排序的第一次迭代吗?

你从左边开始扫描，直到你点击"w"。然后你从右边扫到"r"。然后交换两个元素并继续。当两个扫描器走到一起时，你就停下来。

这是O (n)。

编辑:例如:

int i = 0, j = n-1;
while(true){
  while(a[i]=='r' && i<n) i++;
  while(a[j]=='w' && j>0) j--;
  if (i >= j) break;
  swap(a[i], a[j]);
}

第一个问题是你的算法不正确。如果数组中只有'w'或'r'，您仍然将'w'和'r'同时写入到外循环末尾的数组中。

在这种情况下，你的代码实际上会占用Θ(N²)的时间。假设所有内容都是'r':

char[] A = new char[] { 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r' };
int lastRedPosition = A.Length - 1;
int firstWhitePosition = 0;
for (int i = firstWhitePosition ; i < A.Length; i++)
{
    // determine the first red from the right e.g. the lastred, ending at the firstwhite position
    for (int j = lastRedPosition; j > firstWhitePosition; j--)
    {
        if (A[j] == 'r')
        {
            lastRedPosition = j;
            break;
        }
    }

j现在是A.length - 1 - i。在第一次迭代中，它立即找到了一个'r'，随后，又将i 'w' s写入数组的最后一项，并且lastRedPosition是其中第一个项的索引，因此except for the first iteration, j '只减了一次。

    for (int k = firstWhitePosition; k < lastRedPosition; k++)
    {
        if (A[k] == 'w')
        {
            firstWhitePosition = k;
            break;
        }
    }

firstWhitePosition总是0。k递增到lastRedPosition而没有找到'w'，所以firstWhitePosition 没有改变。因此，k是A.length - 1 - i的增量。

对i求和，求k的~N²/2个增量。

    A[firstWhitePosition] = 'r';
    A[lastRedPosition] = 'w';
}

必须检查A[firstWhitePosition]是否为'w', A[lastRedPosition]是否为'r'。如果没有，你就完蛋了。你的外循环应该检查firstWhitePosition < lastRedPosition

如果您将外部循环转换为while循环，直到firstWhitePosition和lastRedPosition相遇，则更容易看到。很明显，这两个变量一起只遍历数组一次。

仅仅因为整个数组只被遍历一次，并不会自动使它成为O(n)。事实上，在最不理想的情况下(也就是big-O的定义)，整个数组实际上会被遍历两次，第二次遍历发生在外部循环中，使其成为O(n^2)。

如果你能保证数组中只有r和w，那么O(n)方法就是简单地遍历数组一次，计算有多少r和w，然后自己重建数组。这实际上是2次遍历，也就是O(2n)但通常这些系数会被去掉

技术上来说，这是0 (N);然而，从性能的角度来看，它是0 (2N)，这意味着在平均情况下，它的速度是可能的一半。这是因为外部循环对每个元素执行一次，而它们之间的内部循环遍历每个元素，这意味着迭代次数是元素的两倍。

你的想法是对的，但是，如果不是外层循环遍历每个元素，而是在你"知道"所有的r s都在所有w s的左边时就停止呢?

换句话说，从数组的右端开始扫描r(应该在左边)，从左边开始扫描w(应该在右边)。如果w在w的左边，您应该交换它们并继续;但是，如果"最后一个r"的下标位于"第一个w"下标的左边，那么就结束了，应该终止整个函数。相反，您当前的实现一直在循环(和交换)。这就是低效率。我会像Henry建议的那样用while循环替换外部的for循环，终止条件是最后一个r位于第一个w的左侧。

遍历数组一次，计算'r'和'w'的数量，将它们存储为numberR和numberW。将非'r'和'w'字符存储在名为S2的StringBuffer中。
打印numberR 'r's到一个新的StringBuffer S1。将S2追加到S1。
从StringBuffer中获取字符数组

总成本:0 (n)

相关内容

最新更新

热门标签：