在将重复项移动到最后时对数组进行排序？

Question

这是我朋友的编程课中的一个问题.

问:如何对ints 数组进行排序然后排列它们,使得所有重复元素出现在数组的末尾？

例如,给定输入

{5, 2, 7, 6, 1, 1, 5, 6, 2}

输出将是

{1, 2, 5, 6, 7, 1, 2, 5, 6}

请注意,数字已排序,重复数字在7之后,这是数组中的最大值.

这必须通过使用任何Java库包/ utils来实现.

我建议首先使用插入或冒泡排序对数组进行排序,然后遍历数组,执行如下操作:

for (int i = 0; i < nums.length - 2; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        //current and next are same, move elements up
        //and place the next number at the end.
        if (nums[i] == nums[j]) {
            int temp = nums[j];
            for (int k = j; k < nums.length - 1; k++) {
                nums[k] = nums[k + 1];
            }
            nums[nums.length - 1] = temp;
            break;
        }
    }
}

我以后自己尝试了这个(这就是上面的代码) - 当我尝试这个时,我认为这可以通过使用更少的代码,更高效地实现.可能是我提出了错误的建议.

有什么想法吗？

Answer 1

根据问题的参数,有很多方法可以解决这个问题.

如果不允许使用O(n)外部存储器,那么一种选择是使用标准排序算法在O(n log n)时间内对数组进行就地排序,然后对其进行第二次传递.将重复项移到最后(正如您所建议的那样).您上面发布的代码需要O(n ²)时间,但我认为这一步可以使用稍微复杂的算法在O(n log n)时间内完成.这个想法分两步进行.在第一步中,在O(n log n)时间内,您将按排序顺序将所有非重复元素放在前面,并以非排序顺序将所有重复项放到后面.完成后,然后使用第一步中的排序算法在O(n log n)时间内对数组的后半部分进行排序.

我不打算进入代码对数组进行排序.我真的很喜欢排序,但是有很多其他很好的资源可以解决如何对数组进行排序的问题,而不是很好地利用我的时间/空间来进行排序.如果有帮助,这里的链接的Java实现堆排序,快速排序,并smoothsort,所有这些都运行在为O(n log n)的时间.Heapsort和smoothsort仅使用O(1)外部存储器,而quicksort在最坏的情况下可以使用O(n)(尽管良好的实现可以使用可爱的技巧将其限制为O(log n)).

有趣的代码是将所有非重复元素带到范围前面的逻辑.直观地,代码通过存储两个指针来工作 - 读指针和写指针.读指针指向要读取的下一个元素,而写指针指向应放置下一个唯一元素的位置.例如,给定此数组:

1 1 1 1 2 2 3 4 5 5

我们从最初指向1的读写指针开始:

write  v
       1 1 1 1 2 2 3 4 5 5
read   ^

接下来,我们跳过前面的读指针到下一个不是1的元素.这找到2:

write  v
       1 1 1 1 2 2 3 4 5 5
read           ^

然后,我们将写指针碰到下一个位置:

write    v
       1 1 1 1 2 2 3 4 5 5
read           ^

现在,我们将2交换到写指针所持有的位置:

write    v
       1 2 1 1 1 2 3 4 5 5
read           ^

将读指针前进到下一个非2的值:

write    v
       1 2 1 1 1 2 3 4 5 5
read               ^

然后推进写指针:

write      v
       1 2 1 1 1 2 3 4 5 5
read               ^

同样,我们交换'read'和'write'指向的值并向前移动写指针,然后将读指针移动到下一个唯一值:

write        v
       1 2 3 1 1 2 1 4 5 5
read                 ^

再一次收益率

write          v
       1 2 3 4 1 2 1 1 5 5
read                   ^

并且最后的迭代给出了

write            v
       1 2 3 4 5 2 1 1 1 5
read                      ^

如果我们现在从写指针到读指针排序,我们得到

write            v
       1 2 3 4 5 1 1 1 2 5
read                      ^

和宾果游戏!我们得到了我们正在寻找的答案.

在(未经测试,对不起......)Java代码中,此修复步骤可能如下所示:

int read = 0;
int write = 0;

while (read < array.length) {
     /* Swap the values pointed at by read and write. */
     int temp = array[write];
     array[write] = array[read];
     array[read] = temp;

     /* Advance the read pointer forward to the next unique value.  Since we
      * moved the unique value to the write location, we compare values
      * against array[write] instead of array[read].
      */
     while (read < array.length && array[write] == array[read])
         ++ read;

     /* Advance the write pointer. */
     ++ write;
}

该算法在O(n)时间内运行,这导致该问题的整体O(n log n)算法.由于重新排序步骤使用O(1)内存,因此整体内存使用量可以是O(1)(对于类似smoothsort或heapsort的东西)或O(log n)(对于类似quicksort的东西).

编辑:在与朋友讨论之后,我认为基于quicksort的修改,有一个更优雅的解决方案.通常,当您运行快速排序时,最终会将阵列分区为三个区域:

 +----------------+----------------+----------------+
 | values < pivot | values = pivot | values > pivot |
 +----------------+----------------+----------------+

然后递归对第一个和最后一个区域进行排序,以将它们排序.但是,我们可以针对我们的问题版本修改此问题.我们需要作为原语的旋转算法,它在一个数组中取两个相邻的值块并在O(n)时间内交换它们.它不会更改这些块中元素的相对顺序.例如,我们可以使用旋转来转换数组

1 2 3 4 5 6 7 8

成

3 4 5 6 7 8 1 2

并且可以在O(n)时间内完成.

Quicksort的修改版本可以通过使用Bentley-McIlroy三向分区算法(此处描述)来使用O(1)额外空间,将数组元素重新排列为上面显示的配置.接下来,我们应用一个旋转来重新排序元素,使它们看起来像这样:

 +----------------+----------------+----------------+
 | values < pivot | values > pivot | values = pivot |
 +----------------+----------------+----------------+

接下来,我们执行交换,以便将pivot元素的一个副本移动到至少与pivot一样大的元素集中.这可能会有额外的枢轴副本.然后,我们递归地将排序算法应用于<和>范围.当我们这样做时,结果数组将如下所示:

 +---------+-------------+---------+-------------+---------+
 | < pivot | dup < pivot | > pivot | dup > pivot | = pivot |
 +---------+-------------+---------+-------------+---------+

然后我们对该范围应用两个旋转以将其置于最终顺序.首先,使用大于pivot的值旋转小于pivot的重复值.这给了

 +---------+---------+-------------+-------------+---------+
 | < pivot | > pivot | dup < pivot | dup > pivot | = pivot |
 +---------+---------+-------------+-------------+---------+

此时,第一个范围是按升序排列的唯一元素:

 +---------------------+-------------+-------------+---------+
 | sorted unique elems | dup < pivot | dup > pivot | = pivot |
 +---------------------+-------------+-------------+---------+

最后,重复元素的最后一次旋转大于枢轴,并且元素等于枢轴以产生这样:

 +---------------------+-------------+---------+-------------+
 | sorted unique elems | dup < pivot | = pivot | dup > pivot |
 +---------------------+-------------+---------+-------------+

请注意,最后三个块只是已排序的重复值:

 +---------------------+-------------------------------------+
 | sorted unique elems |      sorted duplicate elements      |
 +---------------------+-------------------------------------+

瞧!我们按照我们想要的顺序得到了所有东西.使用与普通快速排序相同的分析,再加上我们只在每个级别进行O(n)工作(三次额外旋转)的事实,在最佳情况下,这可以达到O(n log n)使用O(log n)内存.在具有O(log n)内存的最坏情况下,它仍然是O(n ²),但这种情况发生的概率非常低.

如果允许使用O(n)内存,一个选项是从存储键/值对的所有元素中构建平衡二叉搜索树,其中每个键是数组的元素,值是它出现的次数.然后,您可以按照以下格式对数组进行排序:

1. 对于数组中的每个元素:
   • 如果该元素已存在于BST中,则递增其计数.
   • 否则,使用计数为1的元素向BST添加新节点.
2. 做BST的顺序步行.遇到节点时,输出其密钥.
3. 做BST的第二次顺序步行.遇到节点时,如果它的计数大于1,则输出该节点的n - 1个副本,其中n是它出现的次数.

该算法的运行时为O(n log n),但从头开始编写BST非常棘手.它还需要外部空间,我不确定你是否允许这样做.

但是,如果允许外部空间并且要排序的数组很小并且包含小整数,则可以使用修改的计数排序来修改上述方法.只需将BST替换为足够大的数组,使原始数组中的每个整数成为关键.这将运行时间减少到O(n + k),内存使用率为O(k),其中k是数组中的最大元素.

希望这可以帮助!