C语言 使用单循环从数组中删除重复项

Question

我想用单个循环从数组中删除重复项，它不工作，这就是我目前所做的。

请注意，我已经知道它在排序数组上工作，我使用单循环冒泡排序，但我希望它在没有排序的情况下工作。

code.c

#include <stdio.h>
#define size 20
#define true 1
#define false 0
int main() {

int input[size] = {1, 3, 3, 3, 3, 3, 4, 3, 3, 3, 5, 6, 7, 8, 1, 1, 1, 1, 2, 2};
int current = input[0], flag = false, index = 0;

for (int x = 0; x < size; x++) {
if (current == input[x] && (flag == false)) {
flag = true;
} else if (current != input[x]) {
input[index++] = current;
current = input[x];
flag = false;
}
}

for (int foo = 0; foo < index; foo++) {
printf("%d", input[foo]);
printf((foo != index - 1) ? ", " : "");
}

return 0;
}

输入>

1, 3, 3, 3, 3, 3, 4, 3, 3, 3, 5, 6, 7, 8, 1, 1, 1, 1, 2, 2

1, 3, 4, 3, 5, 6, 7, 8, 1

Answer 1

对于这个问题有几个通用的解决方案:

1. 首先排序数组，然后运行你的算法。这将程序的复杂性增加到O(n log(n))(一般排序算法)或O(n*w)(基数排序，其中w是一个已知的常数，取决于实际类型的大小)，并且不保留原始顺序。换句话说，这个解决方案需要多个循环。

2. 使用映射来检测哪些元素已经发生。一个明显更复杂的解决方案，具有额外的O(log n)复杂度。

3. 如果可能的元素范围很小，例如限制为只有数字0到9，您可以使用布尔数组来跟踪发生的值。这实际上是"地图解决方案"的一个简单版本。这是唯一需要一个循环的选项。代码示例:

#include <stdbool.h>
#include <stdio.h>
#define ARRAY_SIZE 20
int main()
{
int input[ARRAY_SIZE] = {1, 3, 3, 3, 3, 3, 4, 3, 3, 3, 5, 6, 7, 8, 1, 1, 1, 1, 2, 2};
bool hasOccurred[10] = {0}; // The indices are used as keys
size_t newSize = 0U;
for (size_t arrayIdx = 0U; arrayIdx < ARRAY_SIZE; ++arrayIdx)
{
if (!hasOccurred[input[arrayIdx]])
{
hasOccurred[input[arrayIdx]] = true;
input[newSize++] = input[arrayIdx];
}
}
for (size_t idx = 0; idx < newSize; ++idx)
printf("%d%s", input[idx], idx != newSize - 1U ? ", " : "n");
}

输出:

1, 3, 4, 5, 6, 7, 8, 2

4. 使用前面的算法和计数排序的组合。首先，用-1值初始化int hasOccurred[10]数组。然后循环遍历input数组和，对于每个"new"元素，将input数组索引存储在已发生的数组中。这个数组可以用作排序数组(迭代时忽略-1值)，也可以用来构造一个保留原始顺序的输出数组。根据用例的不同，这需要多个循环。

AKX补充说，布尔数组的变化是可能的，例如使用unsigned int的单个位来存储"已发生"。旗帜。这是一个速度/内存的权衡。

感谢pmg建议基数排序。

Answer 2

一种可能的解决方案，在删除重复元素之前使用qsort()对输入数组进行排序，正如上面的评论所建议的那样:

#include <stdio.h>
#include <stdlib.h>
#define ARRAY_SIZE 20
static int _compare(const void * a, const void * b) {
return ( *(int *)a - *(int *)b );
}
int main(void)
{
int data[ARRAY_SIZE] = {1, 3, 3, 3, 3, 3, 4, 3, 3, 3, 5, 6, 7, 8, 1, 1, 1, 1, 2, 2};
int index = 1;

qsort(data, ARRAY_SIZE, sizeof(data[0]), _compare);

for (int i = 1; i < ARRAY_SIZE; i++) {
if (data[i-1] != data[i]) {
data[index++] = data[i];
}
}

for (int i = 0; i < index; i++) {
printf("%d ", data[i]);
}
return 0;
}

控制台输出:

1 2 3 4 5 6 7 8