在O（n）时间内从C / C ++中删除数组中的重复项
假设我有一个像这样的数组
int array[] = {1,1,1,4,5,7,7,9,11}; 我应该能够删除所有重复项，因此我的输出应该是{1,4,5,7,9,11}。
约束：
- 除了变量之外，我不允许使用任何类型的额外内存
- 我应该能够调整arrays的大小
- 我不允许使用像Hashset或set等容器：
- 应该在O（n）时间内完成
如果数组已排序，则可以应用此逻辑。
- 有两个指针（P1，P2）指向数组的开头。
- 增加指针P2。 检查P2和P1指向的值是否相等。
- 如果是，则进一步递增并到达P1和P2指向值不相等的点。 现在转到第5步。
- 如果否，则将P1分配给P2并从步骤2开始重复。
- 现在，删除P1和P2之间的元素。 将P2分配给P1。
重复此过程，直到到达arrays的终点。
遍历数组并将每个元素与前一个元素进行比较。 如果它是相同的，你知道它是重复的。 保留另一个指针，复制数组中的每个唯一元素。 例如。 1,1,4,5,7,7,9,11
在数组的开始处保持两个指针i和j，即1。
使用i遍历数组和j以跟踪唯一元素。 最初，1是唯一的，因此将[i]复制到[j]并递增两者。
下一个1是重复的，所以只增加j。
当遇到4时，它是唯一的，所以将[i]复制到[j]（j指向第二个，即复制1）并递增两者。
做同样的事情，直到我完全遍历arrays。
a [0 … j]给出所有独特元素。
复杂性：O（n）
如果您知道整数的最大值（MAX_INT_VALUE）并且不担心内存限制，这是一个有点创造性的解决方案，让我通过面试：
public int* removeDuplicates(int* array, int arraySize) { short indexMarkers [MAX_INT_VALUE]; int i = 0; for (i=0; i 0) { array[cursor] = i; cursor++; } } //resize array to be sizeof(int)*cursor return array; }
我们的想法是让数组中的项值成为indexMarkers数组的索引。 然后你只是检查是否存在该值以输出新数组。 但这至少是O（2N）。