在将重复项移到末尾时对数组进行排序？
这是我朋友的编程课上的一个问题。
如何排序ints 的数组，然后排列它们，使所有重复的元素都出现在数组的末尾？
例如，给定输入
{5, 2, 7, 6, 1, 1, 5, 6, 2}输出将是
{1, 2, 5, 6, 7, 1, 2, 5, 6}请注意，数字已排序，重复数字在7之后，这是数组中的最大值。
必须 来实现。
我建议先使用插入或冒泡排序对数组进行排序，然后遍历数组，执行以下操作：
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 log
n）时间内就地对数组进行排序，然后对其进行第二次遍历将重复项移到末尾（按照您的建议）。您上面发布的代码需要O（n
2）时间，但是我认为可以使用稍微复杂一些的算法在O（n log n）时间内完成此步骤。这个想法分两个步骤进行。第一步，在O（n log
n）时间中，将所有非重复元素按排序顺序放在最前面，并将所有重复项按非排序顺序放在最后面。完成此操作后，您将使用第一步中的排序算法，以O（n log
n）的时间对数组的后半部分进行排序。
我将不涉及对数组进行排序的代码。我真的很喜欢排序，但是关于如何就地排序数组还有很多其他有用的资源，以至于我在这里没有时间/空间来充分利用它们。如果有帮助，这里的链接的Java实现堆排序，快速排序，并smoothsort，所有这些都运行在O（N
log n）的时间。堆排序和平滑排序仅使用O（1）外部存储器，而快速排序在最坏的情况下可以使用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三向分区算法（在此进行描述）来工作，以便使用O（1）额外空间将数组元素重新排列为上述配置。接下来，我们应用旋转对元素进行重新排序，使它们看起来像这样：
+----------------+----------------+----------------+ | values < pivot | values > pivot | values = pivot |
+----------------+----------------+----------------+
接下来，我们执行交换，以便将枢轴元素的一个副本恰好移到至少与枢轴一样大的一组元素中。这可能在后面有额外的枢轴副本。然后，我们将排序算法递归应用于<和>范围。当我们这样做时，结果数组将如下所示：
+---------+-------------+---------+-------------+---------+ | < pivot | dup < pivot | > pivot | dup > 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 2），但是发生的可能性极低。
一种选择是从存储键/值对的所有元素中构建一个平衡的二进制搜索树，其中每个键是数组的元素，而值是它出现的次数。然后，您可以按照以下格式对数组进行排序：
- 对于数组中的每个元素：
- 如果该元素已存在于BST中，请增加其计数。
- 否则，向BST添加一个新节点，该节点的计数为1。
- 进行BST的有序遍历。遇到节点时，输出其密钥。
- 进行BST的第二次有序步行。遇到一个节点时，如果其计数大于1，则输出该节点的n-1个副本，其中n是它出现的次数。
该算法的运行时间为O（n log n），但是从头开始编写BST会非常棘手。它还需要外部空间，我不确定您是否可以这样做。
但是，如果允许外部空间，并且要排序的数组很小并且包含小的整数，则可以使用修改后的计数sort修改上述方法。只需将BST替换为足够大的数组，以使原始数组中的每个整数都可以用作键。这将运行时间减少到O（n
+ k），内存使用量为O（k），其中k是数组中最大的元素。
希望这可以帮助！
以上是 在将重复项移到末尾时对数组进行排序？ 的全部内容， 来源链接： utcz.com/qa/406192.html
