6

编辑 - 我删除了所有不必要的上下文解释 - 太罗嗦，最终与问题无关。总之，我在构建平衡 KD 树的过程中对坐标数组进行了分区（更多信息请参见维基百科文章的构造部分。我实际上有 n 个项目的 k 个并行数组，每个项目都必须通过相同的比较进行分区）

这不是家庭作业——我写这个问题的目的是为了确保传达所有的细微差别。

给定排序数组：

 int[] ints =  { 0, 1, 2, 3, 4, 5, 6 };
 //this one is important - my current solution fails on this
 int[] ints2 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

请注意，由于一位同事的澄清，这些数组的所有保证element[n]都是小于或等于element[n+1].

对它们的成功操作会将它们分成两个子数组L和R（如下所示）：

/*ints == */  { 1, 3, 5, 0, 2, 4, 6 }
              /*|> L <|  |>   R  <|*/

/*ints2 == */ { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8 }
              /*|>    L    <|  |>    R    <|*/

L包含奇数和R偶数，同时保留这些子数组中这些元素的原始排序顺序。

理想情况下，该函数不会对元素进行重新排序（已经提前执行了冗长的排序操作）并且它不会使用临时数组。我相信这意味着我正在寻找 O(N) 复杂性和 O(1) 内存。

该函数可以提供每个子数组的开始和结束元素 - 即调用者可以提前知道有多少项目将落在左侧/右侧（可能通过提前扫描数组的奇数/偶数）。 在现实中编辑它就像一个数组一样开始；所以在没有这些值的情况下可以工作的解决方案是好的，因为否则如果需要初始通过，完整的解决方案实际上最多只能是 O(2n) 复杂度。

这是我目前的尝试所在 - 我已经更新了它并从原始帖子中评论了它。

public void DivideSubArray(int[] array, int leftStart, int leftCount, 
  int rightStart, int rightCount)
{
  int currentLeft = leftStart, currentRight = rightStart;
  int leftCounter = leftCount;
  int temp;
  int readahead;
  while (leftCounter != 0) {
    if ((array[currentLeft] % 2) == 0)
    {
      //remember the element we swap out
      temp = array[currentRight];
      //Set as next item on the right. We know this is the next lowest-sorted 
      //right-hand item because we are iterating through an already-sorted array
      array[currentRight++] = array[currentLeft];
      // * read ahead to see if there are any further elements to be placed
      // * on the left - move them back one by one till there are no more.
      readahead = currentLeft + 1;
      while ((array[readahead] % 2) != 0)
      {
        array[currentLeft++] = array[readahead++];
        leftCounter--;
      }
      //Now write the swapped-out item in, but don't increment our currentLeft.  
      //The next loop will check if the item is in the correct place.
      array[currentLeft] = temp;
    }
    else //this item is already in the correct place
    {
      currentLeft++;
      leftCounter--;
    }
  }
}

当调用如下：

int numOdd = ints.Count(i => (i % 2) == 1);
DivideSubArray(ints, 0, numOdd, numOdd, ints.Length - numOdd);

ints它为（和许多其他数组）生成预期的数组，但不是ints2：

{ 1, 5, 3, 7, 9, 0, 2, 6, 4, 8 }

所以它正确分区 - 但交换3,5和6,4. 我明白为什么：因为在第一个循环5中被交换到左边，然后2被传播，因为算法说这5是奇怪的并且应该保留。我写了一个可以修复它的决策树，但是在遵循它几个循环之后，它推断出解决方案是递归的。

我正在努力了解如何在不在子数组中运行更多排序操作或创建临时列表/数组作为工作区的情况下解决这个问题。当然，虽然排序可能会增加复杂性，但会保留内存需求；如果事实证明它是最快的解决方案，那么使用它是有意义的。

您可以在我的回答下看到我当前最快（在运行时）和最佳内存解决方案。作为衡量标准 - 上述尝试不仅会产生不正确的结果，而且需要的时间是我答案中代码的 3 倍。

我觉得必须有一种简单的方法来利用单个“备用”变量来交换项目 - 我只是看不到它 - 我希望 SO 集体大脑会:)

当然，如果答案是“不”，那就这样吧。

4

7 回答 7

0

我认为您可以通过以下方式使您的任务更容易：首先修改数组，首先将奇数按升序写入数组的开头，然后将偶数按降序写入最后。对于您的示例 {0,1,...6}，这看起来像 {1,3,5,6,4,2,0}。在你这样做之后，再做一次线性传递来反转数组的第二部分（这非常简单直接）。

为什么我认为这应该更容易？好吧，因为您在第一步中应该做的就是常规 qsort 算法会做的事情（使用有点陌生的比较运算符）。您可以搜索互联网以查看 qsort 分区是如何完成的（例如这里有一个示例）。我真的相信，如果您在这两个步骤上解决问题，那么实施解决方案对您来说会更容易。另请注意，整体复杂性没有改变。

希望这会帮助你。

编辑：这是我相信你可以做我建议的第一部分的方法：

public void DivideSubArray(int[] array, int leftStart, 
              int leftCount, int rightStart, int rightCount)
{
    int currentRight = rightStart + rightCount - 1;

    int current = leftStart;
    while (current < currentRight) {
        if ((array[current] % 2) == 0)
        {
            int temp = array[current];
            array[current] = array[currentRight];
            array[currentRight] = temp;
            currentRight--;
        } else {
            current++;
        }
    } 
}

我没有提供反转偶数部分的代码，因为我相信它非常简单，而且我还想强调这种方法在多大程度上简化了代码。

于 2012-04-26T11:27:26.080 回答
0

我设法找到了一个不使用临时数组的解决方案——对于大 N 来说速度非常慢；我什至不会发布它的代码，那太糟糕了！

编辑 - 这是对我原来的解决方案的改进。复杂性在技术上是 O(2n)（因为 List.CopyTo 方法使用 Array.Copy，根据框架文档，它是 O(n)）并且内存是 O(n)。

是的，该解决方案只是采用数组并即时进行拆分，而不是提前依赖奇数/偶数拆分的知识。这意味着（当回归到我的实际代码时）不需要初始通过 - 所以它是可取的。

这个解决方案很简单：它扫描数组，将赔率移回数组的开头（或者如果它们已经在正确的位置，则将它们留在原处）并将偶数添加到列表中。当循环完成时，列表被复制到数组的其余部分。它以牺牲内存为代价满足了我的复杂性要求——最坏的情况是 O(n)——并且对我已经使用的代码有很大的改进（它比两个列表的解决方案快两倍）。它也不需要初始通过即可获得奇数/偶数拆分。

public void DivideSubArray(int[] array)
{       
    int currentOdd=0;
    List<int> even = new List<int>(array.Length / 2);
    for (int i = 0; i < array.Length; i++)
    {
        if ((array[i] % 2) != 0)
        {
            even.Add(array[i]);
        }
        else
        {
            if (currentOdd != i)
                array[currentOdd++] = array[i];
            else
                currentOdd++;
        }
    }
    even.CopyTo(array, currentOdd);
}

请注意列表的初始容量 - 正如 Mooing Duck 在下面的评论中提到的那样，我可以通过利用一些概率并选择稍高的值来进一步改进（假设平均会观察到大致均匀的分裂）。

也就是说，该算法在偶数拆分时执行最慢 - 如果有更多奇数项目，那么它只是一堆交换。如果有更多的偶数，是的，Add需要更多的操作，但它只会是一个 List 调整大小会影响性能。

我最后一次尝试是看看我是否能实现 izomorphius 建议的 - 以正确的顺序建立赔率，并以相反的顺序或任何顺序建立赔率，而无需额外的数组。如果这是可能的，那么该解决方案将是 O(1) 内存，但 O(n + (排序复杂度)) - 如果它的性能在实践中甚至是上述解决方案的一半，我可能会采用它。

于 2012-04-26T13:08:59.243 回答
0

我不认为有任何“直接”的方式来划分列表而没有一端或另一端被打乱，但仍然可以有一个线性时间常数空间解决方案。izomorphius 提供的分区方法将导致右侧以相反的顺序结束（在线性时间内很容易纠正），而另一端以某种可预测的方式加扰，来自右侧的那些元素混合在一起，以相反的顺序，与来自左侧的那些。可以很容易地在恒定时间内确定给定元素是否来自右侧（只需将其与左侧的最后一项进行比较），然后可以轻松地在线性时间内反转已从右侧移动的元素的顺序右侧到左侧。

一旦这样做了，就会留下一个分区问题，这与原来的非常相似，但只有一半大小；唯一的区别是分割标准是基于节点的值是大于还是小于“原始”最后一个元素，而不是它是偶数还是奇数。因此，人们基本上可以将原始算法应用于较小的数据集。由于可以预先确定拆分的哪一侧将有更多项目，因此可以放置拆分，以便剩余的一侧不超过原始大小的一半。最终结果是，对大小为 2N 的数组进行分区所花费的时间是对大小为 N 的数组进行分区的时间的 O(1) 倍。由于单元素数组可以在恒定时间内完成（显然可以），这意味着将由两个任意混合的排序数据运行组成的任意大小的数组划分为两个不相交的排序数据运行，可以使用常数空间在线性时间内完成。

顺便说一句，虽然整数无关紧要，但需要注意的是，上述算法依赖于比较两个元素并知道第一个元素属于第二个元素的左侧还是右侧的能力。因此它不能用作稳定排序算法的基础。

于 2012-04-27T20:46:45.240 回答
0

我可以在这个线程上尝试一下吗？我可以看到你在说 C#。我不懂语言，但我认为这对这项任务并不重要。

问题描述中缺少一些东西 - 排序数组的来源。可能我应该发表评论要求澄清，但我决定去写一个涵盖我能想到的所有可能性的答案。希望这样的答案将来能为更多的人服务。

基本上，任务将我们放在一个盒子里：“你有一个数组，现在将它拆分到位”。但是，我想稍微解释一下这个数组的起源：

  • 案例 1：从某处读取数组并在代码中排序（内存中）。如果是这种情况，将偶数与赔率分开有一个优雅的解决方案，这不会产生任何开销：
    1. 确定奇数和偶数（通过单次遍历数组O(n)）。
    2. 确定数组中的最大和最小数字。让我们打电话给他们MAXM和MINM。这可以在第一遍中完成以确定偶数和奇数。
    3. 再次通过数组添加MAXM - MINM + 1每个奇数。目标是确保所有奇数都大于偶数。这在时间上是线性的O(n)
    4. 使用 kth_element 算法拆分数组（基本上是快速排序关键分离的单遍）。利用您已经知道每个赔率有多少并且所有赔率都大于所有赔率这一事实，将偶数与奇数分开。该算法以线性时间运行O(n)，但遗憾的是我只有C++ 库实现的参考（没有 C#）。
    5. 遍历奇数对应的所有数组槽，并MAXM - MINM + 1从每个数中减去，得到原始奇数。这在时间上也是线性的O(n)
    6. 最后分别对偶数和赔率部分进行排序。这不会增加整体排序的复杂性，但您会将 to 部分彼此分开。
  • 案例 2：您读取已经从某个持久存储中排序的数组，例如硬盘上的文件，并提前知道奇数和偶数的数量。
    1. 在这种情况下，您只需要在输入数字的数组中放置：一个用于下一个跟随偶数，一个用于下一个跟随奇数。这个解决方案应该是显而易见的，它根本不会影响性能。
  • 情况 3：您读取了已经从某个持久存储中排序的数组，例如硬盘上的文件，但事先不知道奇数和偶数的数量。
    1. 从数组的开头开始填充偶数，从数组的末尾开始填充赔率。这样，最后两个序列将在中间相遇。
    2. 因此，您将把偶数从赔率中拆分出来，但奇数将按降序排列，而不是增加。您只需对奇数部分（也是线性的）进行就地反转，您就拥有了所需的数组。

希望至少有一个所描述的场景适合您，并且您将能够使用其中的想法解决您的问题。

于 2012-04-28T17:27:30.827 回答
0

我认为，可能存在 O(n) 时间和 O(1) 空间算法。但它可能太复杂了，我们无法理解。

我将通过以下方式说服您：

  1. 向您展示原始问题的一个特例，我们称之为 A。
  2. 考虑问题 A 的反面，我们称其为问题 B。并证明如果我们得到其中任何一个的 O(n) 时间和 O(1) 空间解，那么我们可以修改它来解决另一个问题。
  3. 我将向您展示问题 B 可以在 O(n) 时间和 O(1) 空间内解决，但解决方案非常复杂，需要大量数学运算。

所以这意味着，您的问题不太可能得到简单的解决方案，否则我们可以轻松解决问题 B。

1.考虑一个特殊情况：

令 A[] = {1,2,3,4,5,6,7,8}，从 1 到 2n，在本例中 n = 4。所以你想把它改成{1,3,5,7,2,4,6,8}，对吧？我们称之为问题 A。一般来说，这意味着您有一个大小为 2n 的数组 A，从 A[1] 到 A[2n]，您想将其重新排列为 A[1],A[3],A[ 5]...,A[2n-1],A[2],A[4],A[6],A[2n]。这是您的问题的一个特例。如果你找到了问题的解决方案，那么问题 A 就很容易解决。

2.问题A的反面。

让我们考虑一个相关的问题。令 B = {1,2,3,4,5,6,7,8}，我们想将其更改为 {1,5,2,6,3,7,4,8}。这就像你有一副纸牌，你想做一个完美的洗牌，把它们分成两等份，然后交替合并。所以一般来说，你有一个大小为 2n 的数组 B，从 B[1] 到 B[2n]。您想将其重新设置为 B[1],B[n+1],B[2],B[n+2],....B[n],B[2n]。

然后你就会意识到问题A和问题B是逆运算。也就是说，对于一个大小为 2n 的数组，如果先做 B 操作，再做 A 操作，就会变成原来的数组，同样先做 B 再做 A。

如果你对置换有一定的了解，你就会知道，如果我们得到一个 A 的算法，那么我们可以改变它，使它适用于 B。如果你不熟悉这个，我可以稍后再详细说明。

3.问题B不容易解决。

问题 B 是否存在 O(n) 时间和 O(1) 空间算法。确实存在，您可以查看Computing the Cycles in the Perfect Shuffle Permutation。这是一篇 12 页的论文，这意味着你不太可能在面试中提出这个解决方案。我读过它，它确实需要大量的数论数学。这更像是一个理论上的解决方案。

结论：

似乎没有一个简单的（这意味着不需要 10 页纸）O(n) 时间 O(1) 空间解决您的问题，即使对于问题 A 中的特殊情况也是如此。否则我们可以将其修改为解决问题 B。我不确定您的广义问题是否有 O(n) 时间 O(1) 空间解决方案。

如果你真的对这个问题感兴趣。你可以看看 Knuth 的 The Art of Computer Programming。有一章讨论原位置换。

理解我的想法可能并不容易，所以如果您有任何问题，请发表评论。

于 2012-04-29T18:54:30.447 回答
0 
// stable_partition.cpp
// example general inplace stable partition.

#include <algorithm>
#include <functional>
#include <iterator>
#include <iostream>
#include <vector>

template<typename Fwd, typename Pred>
  Fwd
  inplace_stable_partition(Fwd first, Fwd last, Pred pred)
  {
    ptrdiff_t nmemb = std::distance(first, last);

    if (nmemb == 1)
      return pred(*first) ? last : first;
    if (nmemb != 0)
      {
        Fwd split = first;
        std::advance(split, nmemb/2);

        first = inplace_stable_partition(first, split, pred);
        last = inplace_stable_partition(split, last, pred);

        std::rotate(first, split, last);
        std::advance(first, std::distance(split, last));
      }
    return first;
  }

int
main(int argc, char* argv[])
{
  using namespace std;

  vector<int> iv;
  for ( int i = 0; i < 10; i++ )
    iv.push_back(i);

  copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
  cout << endl;

  inplace_stable_partition(iv.begin(), iv.end(), bind2nd(modulus<int>(), 2));

  copy(iv.begin(), iv.end(), ostream_iterator<int>(cout, " "));
  cout << endl;
  return 0;
}
于 2012-08-02T17:33:26.940 回答
-1

看起来您正在寻找一种稳定的就地排序算法，它具有特殊的元素关系顺序（任何奇数都小于任何偶数）。

鉴于此，我认为你不能比 O(n ln n) 更好。

我会进行就地合并排序。

如果您不需要保留具有相同值的元素的顺序，请使用快速排序，这对于就地处理要简单得多（但是，对于数十亿个元素，这可能不太适合）。

于 2012-04-26T11:53:41.753 回答