0

我正在处理一些算法分配，并被问到以下问题：在 O(n) 中对一个数组进行排序，其中元素 'r' 或 'w' 就位，因此 'r' 总是在 'w' 之前。因此，如果输入看起来像 [w,r,w,r,w,r,w,w]，则在算法运行后数组看起来像 [r,r,r,w,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 循环......有人可以给我一些指向正确directopm的指针吗？

4

6 回答 6

4

这不只是快速排序的第 1 次迭代吗？

你从左边扫描直到你点击'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]);
}
于 2013-01-07T19:27:39.400 回答
2

第一个问题是您的算法不正确。如果数组中只有'w's 或只有'r's，您仍然在外循环结束时将a'w'和 an写入数组。'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没有找到 a 'w'，因此firstWhitePosition 不会更改。因此k是递增的A.length - 1 - i次数。

总和i的~N²/2增量为k。

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

您必须检查是否A[firstWhitePosition]实际是'w'和A[lastRedPosition]实际'r'。如果没有，你就完成了。你的外循环应该检查firstWhitePosition < lastRedPosition.

于 2013-01-07T20:09:24.677 回答
1

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

如果您可以保证数组中只有 r 和 w，则 O(n) 方法只是遍历数组一次，计算有多少 r 和 w，然后自己重​​建数组。这实际上是 2 次遍历，使其成为 O(2n)，但通常这些系数会被丢弃。

于 2013-01-07T19:00:14.153 回答
1

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

于 2013-01-07T19:00:36.457 回答
0

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

您的想法是正确的，但是如果不是遍历每个元素的外部循环，而是在您“知道”所有rs 都在所有 s 的左侧时就停止了w呢？

换句话说，您首先从数组的右端扫描一个r（应该在左边），从左边扫描一个w（应该在右边）。如果 位于w左侧w，则应交换它们并继续；但是，如果您的“最后一个 r”索引位于“第一个 w”索引的左侧，那么您就完成了，应该终止整个函数。相反，您当前的实现会不断循环（和交换）。这就是效率低下。正如亨利建议的那样，我会用 while 循环替换外部 for 循环，终止条件是 lastr在 first 的左侧w。

于 2013-01-07T19:03:42.467 回答
0

  1. 遍历数组一次，计算 'r' 和 'w' 的数量，将它们存储为 numberR 和 numberW。将非 'r' 和非 'w' 字符存储在名为 S2 的 StringBuffer 中。

  2. 将 numberR 'r's 打印到新的 StringBuffer S1 中。将 S2 附加到 S1。将 numberW 的 'w' 附加到 S1。

  3. 从 StringBuffer 中获取字符数组。

总成本：O(n)

于 2013-01-08T22:03:54.250 回答