我在一次面试中被问到了这个问题。有一个带重复元素的已排序数组，目标是返回只含唯一元素的数组，后面跟着重复元素，且保持原来的顺序。例如[1, 1, 2, 3, 4, 4, 5]应该变成[1, 2, 3, 4, 5, 1, 4]。
我使用了额外的空间（O(n)空间）和线性时间（O(n)时间）来解决这个问题，但我不确定这是否是最好的答案，理想情况下不使用线性空间。
我在stack overflow上搜索到了类似的问题，但并不完全相同。例如，有一个问题是将数组排序并将重复元素移动到末尾，但在我的情况下，数组已经排好序，目标只是将重复元素移到末尾。
如果你的数值范围有限，那么可以在O(n)时间和O(1)空间内找到解决方案。
确定数组中的最大值。选取某个常量C>arraymax，例如，对于你的数组，C=10。
扫描数组，将唯一的值压缩并计算每个值的重复次数。如果值V有K>0个副本，则写入V+C*K而不是该值。
在下一次扫描中，查找具有重复项的值，提取重复项的数量，并在压缩的唯一值之后写入它们。
def dedup(lst):
mx = max(lst) + 1
dupcnt = 0
delcnt = 0
start = 0
for i in range(1, len(lst) + 1):
if i == len(lst) or (lst[i] != lst[start]):
lst[start - delcnt] = lst[start] + dupcnt * mx
delcnt += dupcnt
start = i
dupcnt = 0
else:
dupcnt += 1
dupidx = len(lst) - delcnt
for i in range(0, len(lst) - delcnt):
dupcnt = lst[i] // mx
if dupcnt:
lst[i] %= mx
for j in range(dupidx, dupidx+dupcnt):
lst[j] = lst[i]
dupidx += dupcnt
return lst
print(dedup([1,2,2,2,3,4,4,5]))
>>> [1, 2, 3, 4, 5, 2, 2, 4]
~2*N操作=O(N)。嵌套循环的算法通常具有二次行为。 - MBo您需要有2-3个指针（索引）：
i: 下一个唯一元素将放置在此位置j: 列表上的线性遍历指针private static void fix(int[] nums) {
int i = 0;
int j = 0;
while (j < nums.length) {
int k;
for (k = j + 1; (k < nums.length) && (nums[k] == nums[j]); k++) {}
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
j = k;
i++;
}
}
更新：我误读了您的意图，您关心的是空间问题，这是“指针”的PHP版本。由于它已经排序，我们只需要遍历一次循环，对吧？如果不是，我们可能会将重复排序嵌入到排序本身中。
function findRepeating(&$arr)
{
$size = count($arr);
$previous = -99999;
for ($i = 0; $i < $size; $i++) {
if ($i>0)
$previous = $arr[$i-1];
if ($arr[$i] == $previous) {
array_push($arr,$arr[$i]); //push to end
unset($arr[$i]); //then remove current one
}
}
var_dump($arr);
}
array(7) {
[0]=>
string(1) "1"
[2]=>
string(1) "2"
[3]=>
string(1) "3"
[4]=>
string(1) "4"
[6]=>
string(1) "5"
[7]=>
string(1) "1"
[8]=>
string(1) "4"
}
对于如何处理多个重复项或者你确切的问题不是很清楚，但我猜测你想要确保满足O(1)空间复杂度，无论时间复杂度如何，所以我会尝试回答这个问题。
你可以通过将重复元素交换到末尾来原地进行操作。你可以通过保持一个“当前”指针并简单地检查“下一个”元素是否与“当前”相同来找到重复元素。在最坏情况下，这需要O(n^2)时间。例如：
[1,1,2,3,4,4,5] # "cur" is index 0 (element 1), and "next" is index 1 (element 1). Swap "next" to end.
[1,2,1,3,4,4,5] # swapping
[1,2,3,1,4,4,5] # swapping
... # Tedious swapping
[1,2,3,4,4,5,1] # Done swapping. Increment "cur".
[1,2,3,4,4,5,1] # "cur" is index 1 (element 2), and "next" is index 2 (element 3). Increment "cur"
... # Boring (no duplicates detected)
[1,2,3,4,4,5,1] # "cur" is index 3 (element 4), and "next" is index 4 (element 4). Swap "next" to end.
[1,2,3,4,5,4,1] # swapping
[1,2,3,4,5,1,4] # Done swapping. Increment "cur"
... # No more duplicates
# Done
顺便提一下，在实践中，为了节省空间而牺牲时间通常是不值得的。内存很便宜，但慢的响应时间可能会失去用户，这是很昂贵的。一个值得注意的例外是嵌入式系统，其中内存可能很紧张，输入很短（在小输入上渐近运行时间不相关）。
如果您有一个链表而不是数组，您可以很容易地在 O(n) 时间和 O(1) 空间内完成此操作。 当你被迫“移动”元素时，链表比数组更具优势，因为它们可以移动指针而不是将所有元素移动一个位置。 cur/next 策略与上面的数组类似。以下是一个示例：
1->1->2->3->4->4->5 # "cur" is first element (value 1), and "next" is second element (value 1). Swap "next" to the end.
1
\
1->2->3->4->4->5 # Move "cur"'s pointer to "next"'s next element.
1->2->3->4->4->5->1 # Set "next"'s pointer to null, set tails pointer to "next"
... # Boring stuff with no duplicates
1->2->3->4->4->5->1 # "cur" is fourth element (value 4), and "next" is fifth element (value 4). Swap fifth element to end.
4
\
1->2->3->4->5->1 # Move "cur"'s pointer to "next"'s next element.
1->2->3->4->5->1->4 # Set "next"'s pointer to null, set tails pointer to "next"
... # No more duplicates
# Done (hopefully it's clear moving and element to the end is O(1) instead of O(n))
如果您可以在O(n)时间和O(1)空间内将数组转换为链表，则问题解决了。然而，这是不可能的。 链表每个元素占用的空间比数组多，因此仅通过程序中存在链表，我认为O(1)空间就会被破坏。
虽然这是一个面试问题，但指出链表更适合高效地解决此问题可能是值得的，无论问题陈述如何。通常，面试官喜欢看到您能够正确应用数据结构，有时他们也会接受输入类型的更改。
聪明的数据结构和愚蠢的代码比另一种方式要好得多。--Eric S Raymond
void put_dublicates_to_last(char**s, int n)
{
int i = 0, j = 0, flag = 0,counter=0;
int* indicator = malloc(n * sizeof(int));
char * temp;
for (i = 0; i < n; i++)
indicator[i] = -1;
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (strcmp(s[i], s[j]) == 0)
{
//swap with the last element
counter++;
indicator[j] = 0;
}
}
}
printf("counter is %d\n", counter);
//use the indicator to swap with the last elements
for (i = 0; i < n; i++)
{
for (j = n; j >= 0; j--)
{
if (indicator[i] == 0)
{
if (indicator[j] != 0)
{
//swap
temp = s[i];
s[i] = s[j-1];
s[j-1] = temp;
flag = 1;
}
}
if (flag)
{
flag = 0;
break;
}
}
}
for (i = 0; i < n; i++)
printf("%s\n", s[i]);
}
如果我们不介意数组中重复元素的稳定性和排序性，可以用单指针和另一个指针来找到下一个最大值。
算法
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {11, 12, 12, 13, 14, 14, 14, 14, 15};
rearrangeSort(arr);
for(int a : arr) {
System.out.print(a + " ");
}
}
public static void rearrangeSort(int[] arr){
int unique = 1;
int find = 0;
while(unique < arr.length) {
if(unique == 1 && (arr[unique - 1] == arr[unique])){
find = findMax(arr, arr[unique], unique);
swap(arr, unique, find);
}else if(unique == 1 && (arr[unique] == arr[unique + 1])){
find = findMax(arr, arr[unique], unique);
swap(arr, unique + 1, find);
}
if(unique > 0 && (arr[unique - 1] < arr[unique]) && (arr[unique] < arr[unique + 1])){
unique++;
}
find = findMax(arr, arr[unique], unique);
if(find == 0) {break;}
swap(arr, unique+1, find);
}
}
public static int findMax(int[] arr, int target, int index){
while(index < arr.length) {
if(arr[index] > target) {return index;}
index++;
}
return 0;
}
public static void swap(int[] arr, int idx1, int idx2){
int temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
}