删除数组中迭代的问题

在这段代码中，我试图从数组中删除指定值的所有匹配项。函数应该有三个参数，数组，数组长度和正在搜索的值。每次找到该值时，都应该移动数组以移除该值。删除数组中迭代的问题

这是我到目前为止有：

void arrayShift(int arr[], int length, int value){ 
    for(int i = 0; i<length; i++) 
     { 
     if(arr[i] == value) 
      { 
      for (int k = i; k<length ; k++) 
       { 
        arr[k] = arr[k+1]; 
       } 
      arr[length-1] = 0; 
      } 
     } 
}

的代码是成功的，当这些是使用的值：

int inputarray[] = {10,20,30,40,50,10}; 
int length = 6; 
int value = 10; 
//output: 20 30 40 50 

int inputarray[] = {6, 7, 8, 9}; 
int length = 4; 
int value = 6; 
//ouput: 7 8 9 

int inputarray[] = {10,20,30,40,50,60}; 
int length = 6; 
int value = 70; 
//output: 10 20 30 40 50 60

但是，代码不工作时：

int inputarray[] = {9,8,9,9,9,9,6}; 
int length = 7; 
int value = 9; 
//what I get: 8 9 
//what I want: 8 6

我似乎无法弄清楚为什么我的代码在迭代播放时失败。

来源

2015-03-13 McRhook

http://en.cppreference.com/w/cpp/algorithm/remove – 2015-03-13 12:10:27

在每个迭代中（可能）移动整个（尾部）数组会导致程序的平方时间复杂度O（n^2）。看到我的答案是线性时间方法。 – CiaPan 2015-03-13 13:11:07

这是固定的O（n^2）算法。对于线性复杂性，请参阅CiaPan的答案。

void arrayShift(int arr[], int length, int value) 
{ 
    for(int i = 0; i < length; i++) 
    { 
     if(arr[i] == value) 
     { 
      for (int k = i; k < length ; k++) // condition should be k + 1 < length, otherwise k + 1 is out of bounds 
       arr[k] = arr[k + 1]; 

      i--;  // you want to decrement i here cause current element has been removed, thus i is already index of the next element 
      length--; // you should also decrement length 
      arr[length] = 0; 
     } 
    } 
}

你也应该返回新的长度，或通过引用传递长知道后的尺寸...

来源

2015-03-13 08:29:59 LogicStuff

谢谢！看着解决方案，我觉得有点傻，甚至没有尝试。 – McRhook 2015-03-13 08:32:13

不要忘记返回阵列使用部分的新大小。 – LogicStuff 2015-03-13 08:34:30

O（n^2）清空数组，如果它包含所有项目等于'值' – CiaPan 2015-03-13 08:44:04

当i = 1阵列是{8,9,9,9,9,6,0}和array[i]正在看第一个9。

当i = 2阵列是{8,9,9,9,6,0,0}和array[i]正在看第二个9。

由于i只会从这一点开始向前移动，所以没有办法摆脱当前函数中阵列中的第一个9。

来源

2015-03-13 08:21:15 ajarusan

的问题是一样ajarusan说，

让我们解释一下。

针对码

int inputarray[] = {9,8,9,9,9,9,6}; 
int length = 7; 
int value = 9;

对于i=0，arr[i]是9并且它被交换和阵列变得

8 9 9 9 9 6 
^ 
i=0

现在对于i=1，arr[i]是9并且它交换。交换之后的阵列成为

8 9 9 9 6 
^
    i=1

但随后，它进入到下一个i=2及使该9索引1在被跳过。在指数2调换9后，数组变为

8 9 9 6 
    ^
    i=2

正如你所看到的，9在i=1没有改变。这是导致问题的原因。

为了解决这个问题只需添加一个i--这里

void arrayShift(int arr[], int length, int value){ 
    for(int i = 0; i<length; i++) 
     { 
     if(arr[i] == value) 
      { 
      for (int k = i; k<length ; k++) 
       { 
        arr[k] = arr[k+1]; 
       } 
      arr[length-i] = 0; // I changed to length - i 
      i--;     // added i-- 
      } 
     } 
}

好表示，这应该解决的问题。

来源

2015-03-13 08:38:48

扫描阵列并将与value不同的项目复制到阵列的开头。
变量j是一个复制目标索引，因此它在每个副本上增加。
j的最终值是一个复制项目的数量，这是一个结果数组长度 - 返回它，所以一个调用者知道它可能使用的部分arr[]。

int arrayShift(int arr[], int length, int value){ 
    int j = 0; 

    for(int i = 0; i<length; i++) 
     if(arr[i] != value) 
      arr[j++] = arr[i]; 

    /* you may also zero the tail of array, 
     but it doesn't seem necessary if you return j 
    */ 
    for(i=j; i<length; i++) 
     arr[i] = 0; 

    return j; // new length 
}

来源

2015-03-13 08:41:45 CiaPan

你常犯的错误：你已经习惯通过与for循环，你还没有真正通过自己在做什么想数组迭代。

如果阵列是这个

1 2 3 4 
^

，你正在寻找在指定的元素，如果你不想删除你提前

1 2 3 4 
    ^

但是，如果不是你想删除它，你改变数组

1 3 4 
^

，现在你不想要前进，因为你已经在下一个元素。因此，您必须制作比平时不同的循环结构（您可能需要使用while），以便您只有在不删除元素时才能使其前进。

来源

2015-03-13 12:07:35 Hurkyl

删除数组中迭代的问题

回答

相关问题