无法删除数组中的迭代

Question

在此代码中，我试图从数组中删除所有出现的指定值。函数应采用三个参数，数组、数组长度和要搜索的值。每次找到值时，都应移动数组以删除该值。

这是我目前拥有的：

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

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

Answer 1

当 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的。

Answer 2

这是您修复的 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;
        }
    }
}

您还应该 return 新长度，或通过引用传递长度以了解之后的尺寸...

Answer 3

问题正如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，这会导致索引 1 处的 9 被跳过。交换索引 2 处的 9 后，数组变为

8 9 9 6
    ^
    i=2

如您所见，i=1 处的 9 没有改变。这就是导致问题的原因。

要解决此问题，只需按此处所示添加 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--
           }
        }
}

嗯，那应该可以解决问题。

Answer 4

扫描数组并将不同于value的项目复制到数组的开头。
变量 j 是复制目标索引，因此它会在每次复制时递增。
j 的最终值是复制项的数量，即结果数组长度 – return 它，因此调用者知道它可能使用 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
}

Answer 5

您犯了一个常见错误：您太习惯于使用 for 循环遍历数组，以至于您没有真正考虑过自己在做什么。

如果你的数组是这样的

1 2 3 4
  ^

并且您正在查看指示的元素，如果您不想删除它，请前进

1 2 3 4
    ^

但是如果您想删除它，您可以将数组更改为

1 3 4
  ^

现在你不想前进，因为你已经在下一个元素了。

因此，你必须创建一个不同于平常的循环结构（你可能想使用 while），这样你就可以告诉它只有在你不删除元素.

无法删除数组中的迭代

Trouble deleting iterations in array

c++

arrays

iteration