自定义排序数组

Question

您有一组数字。 a1, a2, a3, a4, ..., an 。这些数字是随机的并且可能重复。

按顺序排列数字，使 x1 > x2 < x3 > x4 < x5 > x6 ... .

x1与 x3, x4, x5, ... 没有关系, x2与 x4, x5,... 没有关系, x3与 x1, x5, x6,... 没有关系等等。

这个问题可能有很多可行的解决方案，看看最终的答案到达其中的任何一个。如果输入像 22,22,22那么它应该输出一条消息“没有可行的解决方案”，但对于像 7 7 7 3 3 这样的输入它应该打印出如下解决方案: 7 3 7 3 7 .

我的解决方案是首先按 O(nlogn) 对输入数组进行排序，然后用最后一个未触及的元素填充输出数组，然后用第一个未触及的元素填充输出数组，因此总体 O(nlogn) 。我们能做得更好吗？如何跟踪不可行的解决方案？

Answer 1

• 你显然排除了平等。因为所有同等的项目不能这样排列。因此，如果某些内容等于就绪序列的当前结尾，我们将丢弃它。

  1. 取a1,a2。其中有人更伟大。这将是第一个。
  2. 现在我们需要比上一个更大的项目。如果下一个a大于最后一个x，则让a成为下一个x。如果下一个a小于最后一个x，则将当前a放在最后一个x位置，并且x移动到下一个位置。
  3. 与 2 相同，只是变大变小，反之亦然。
  4. 返回2。

  5. 在输入数组 a 末尾退出。

     a:7,10,5,8,9

     x: 10,7     ?5

     x: 10,5,7     ?8

     x: 10,5,8,7     ?9

     x:10,5,8,7,9

复杂度为 O(n)。但你不应该忘记清理掉相同的元素。您可以在选择下一个项目的同时获得随机数并丢弃与前一个数字相同的数字。您无需创建 a 的数组。无论如何，它们都是随机的。