问：如何对一组int进行排序,然后对它们进行排列,以便所有重复的元素出现在数组的末尾？
例如,给定输入
{5,2,7,6,1,5,2}
输出将是
{1,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;
}
}
}
我以后自己尝试了这个(这就是上面的代码) – 当我尝试这个时,我认为这可以通过使用更少的代码,更高效地实现.可能是我提出了错误的建议.
有什么想法吗？
解决方法
如果不允许使用O(n)外部存储器,那么一种选择是使用标准排序算法在O(n log n)时间内对数组进行就地排序,然后对其进行第二次传递.将重复项移到最后(正如您所建议的那样).您上面发布的代码需要O(n2)时间,但我认为这一步可以使用稍微复杂的算法在O(n log n)时间内完成.这个想法分两步进行.在第一步中,在O(n log n)时间内,您将按排序顺序将所有非重复元素放在前面,并以非排序顺序将所有重复项放到后面.完成后,然后使用第一步中的排序算法在O(n log n)时间内对数组的后半部分进行排序.
我不打算进入代码对数组进行排序.我真的很喜欢排序,但是有很多其他很好的资源可以解决如何对数组进行排序的问题,而不是很好地利用我的时间/空间来进行排序.如果有帮助,这里是heapsort,quicksort和smoothsort的Java实现的链接,所有这些都在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)时间内完成.
快速排序的修改版本可以通过使用Bentley-McIlroy三向分区算法(描述here)来工作,使用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(n2),但这种情况发生的概率非常低.
如果允许使用O(n)内存,一个选项是从存储键/值对的所有元素中构建平衡二叉搜索树,其中每个键是数组的元素,值是它出现的次数.然后,您可以按照以下格式对数组进行排序：
>对于数组中的每个元素：
>如果该元素已存在于BST中,则递增其计数.
>否则,使用计数为1的元素向BST添加新节点.
>做BST的顺序步行.遇到节点时,输出其密钥.
>做BST的第二次顺序步行.遇到节点时,如果它的计数大于1,则输出该节点的n – 1个副本,其中n是它出现的次数.
该算法的运行时为O(n log n),但从头开始编写BST非常棘手.它还需要外部空间,我不确定你是否允许这样做.
但是,如果允许外部空间和要排序的数组很小且包含小整数,则可以使用修改后的counting sort修改上述方法.只需将BST替换为足够大的数组,以便原始数组中的每个整数都可以是关键.这将运行时间减少到O(n k),内存使用率为O(k),其中k是数组中的最大元素.
希望这可以帮助！
