算法，从数组删除重复不起作用

我有一个字符数组，有一些重复的值：算法，从数组删除重复不起作用

A B C D E F E A

这是我的算法删除重复值：

char array[20] = {'A', 'B', 'C', 'D', 'E', 'F', 'E', 'A'}; 
int length = 8; 

    for (int i = 0; i < length; i++) 
    { 
     for (int j = i + 1; j < length - 1; j++) 
     { 
      if (array[i] == array[j]) 
      { 
       array[j] = array[j + 1]; 
       length--; 
      } 
     } 
    } 

EXPECTED OUTPUT: A B C D E F 
OUTPUT: A B C D E F A

我试图在论文中运行这个算法，看起来没问题，但是当我以书面形式做这件事时，却无法在我的应用程序中运行。

来源

2014-11-04 Evaldas B

我猜'counter'是结果长度。 – 2014-11-04 13:39:02

抱歉，我在这里发帖时没有重写过。它应该是长度而不是计数器。 – 2014-11-04 13:40:27

您的“重复删除”步骤可靠地创建新副本。而不是'a [j] == a [i]'你现在有'a [j] == a [j + 1]'。始终 – 2014-11-04 13:44:17

您应该添加一个for循环中的if语句检查下面的代码：

char array[20] = {'A', 'B', 'C', 'D', 'E', 'F', 'E', 'A'};

INT长度= 8;

for(int i = 0; i <= length; i++){ 

     for(int j = i+1; j <= length; j++){ 

       if(array[j] == array[i]){ 

          for(int x = j+1; x <=length; x++){ 

            array[j]=array[x]; 

            } 
          length--; 
          } 

       } 

     } 

for(int z = 0; z <= length; z++){ 
     cout << array[z] << " "; 
     } 
     cout << endl;

来源

2014-11-04 16:06:58 SilverS

j < length允许[j + 1]超越长度

作为元件移动，length不再有效数据的长度。 counter可能是，但你不显示代码是如何初始化的。

问题编辑使用length--代替counter--但误差在推进j一路在其中包含一个j + 1内环的端部。由于内环设置喷射到i + 1

来源

2014-11-04 13:41:58

所以在第一个循环中设置我 2014-11-04 14:02:03

您还有没有必要延长i一直到length您有未定义的行为。

在外循环（i = 0）和内循环（j = 7，其中length = 8）的最后一次迭代中，array[i] == array[j]为真，因为它们都是'A'。但是，你访问array[j+1]，这是超出界限。

然后，当i = 4和j = 6时，您将值7复制（现在用垃圾覆盖，但显然恰好是您的情况中的'A'）到索引6，给出了错误的结果看到。

您需要复制条件为j < (length - 1)的元素以避免UB。那么你至少应该在这个例子中得到正确的结果。

来源

2014-11-04 13:44:04

问题编辑揭示：真实数据后有额外空间，包含NUL。 – 2014-11-04 13:45:45

我已经改变j <长度为j <（长度 - 1），输出是A B C D E F A – 2014-11-04 13:46:41

@EvaldasB好吧，那也是错误的。你需要检查最后一个元素，但是你不应该复制它。 – 2014-11-04 13:47:35

虽然我知道这并不直接解决的问题，这里是更好的代码替代，通过它可以避免此类问题（需要下的初始化向量++ 11）：

std::vector<char> in{'A', 'B', 'C', 'D', 'E', 'F', 'E', 'A'}; 
std::vector<char> out; 

std::sort (in.begin(),in.end()); 

std::unique_copy(in.begin(), in.end(), std::back_inserter(out));

如果您不需要副本，也可以使用std::unique而不是std::unique_copy。

来源

2014-11-04 14:04:01 davidhigh

'std :: unique_copy'只删除连续重复的 – 2014-11-04 14:17:00

谢谢您的评论。所以人们必须提前做一个排序。 – davidhigh 2014-11-04 14:20:10

你必须排序'在'，而不是'':) – 2014-11-04 14:29:20

它仅适用从i = 0到3。

在i = 4，阵列[4] = 'E'，阵列[J] = 'F'，它通过。 j ++ 当i = 4时，array [4] ='E'，array [j] ='E'，array [j]设置为数组[j + 1]，即'A'。

移位工作正常，但对于我的循环可能是数组的整体长度而不是改变长度，因为它在i = 5时停止。

来源

2014-11-04 14:28:17 sereneL

算法，从数组删除重复不起作用

回答

相关问题