arrays - 从 C 中的数组中删除给定数字的所有出现

Question

我正在尝试解决这个问题:

You've got an array of integers of somewhat SIZE - i.e, arr[SIZE]. Write a function which remove all occurrences of a given number x from an array

我写了这个函数(如下)，它适用于数字为 1 且仅出现但不适用于多次的情况，我正在努力为最后一种情况(多次出现)寻找突破口。我的想法是:在匹配的情况下 - 左移一个索引匹配右侧的所有元素并返回用户"new"尺寸。

例如:{ 3, 0, 5, 6, 6 };结果将是数字 5(实际上是):{ 3, 0, 6, 6 } ，但是对于:{ 3, 0, 5, 5, 6 }，我有:{ 3, 0, 5 , 6}。我知道为什么我得到它，但我不知道如何解决它。我尝试使用一个标志，它会指示我是否有两个相邻的匹配元素，以及它是否再次在此索引上循环

有人可以指导我解决问题吗？

#include <stdio.h>

#define SIZE    5
int arr[SIZE] = { 3, 0, 5, 6, 6 };

int remove_occurences(int x)
{
    int i, j;
    int removed = 0;

    for (i = 0; i < SIZE; i++)
    {
        if (arr[i] == x)
        {
            removed++;
            for (j = i; j < (SIZE - 1) ;j++)
            {
                arr[j] = arr[j+1];
            }
        }
    }
    return (SIZE - removed);
}

int main()
{
    int new_length;
    int i;

    new_length = remove_occurences(5);
    for (i = 0; i < new_length; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

谢谢

Answer 1

问题在于，通过将所有元素向后移动一个位置来移除数组元素后，内部循环从迭代 i + 1 开始。这就是为什么:

{ 3, 0, 5, 5, 6 }

您将删除第一个 5

{ 3, 0, x, 5, 6 }

移动数组的元素:

{ 3, 0, 5, 6, x}

但现在您应该从 i 位置重新开始，而不是 i+1。 否则，您将跳过当前的第二个 5。此外，每次删除一个元素时，您都需要调整SIZE，即:

int remove_occurences(int x){
    int i = 0, j;
    int total_elements = SIZE;
    while (i < total_elements){
        if (arr[i] == x){
            for (j = i; j < (total_elements - 1) ;j++)
                arr[j] = arr[j+1];
             total_elements--; // We have one element less now
        }
        else
           i++; // Only increment if you did not remove elements from the array
    }
    return total_elements;
}

在最坏的情况下，该算法的时间复杂度为 O(N^2)，其中 N 是数组的大小。尽管如此，还是有一种具有线性时间复杂度的算法(即 O(N))，如我们所见here以及关于“Nishad C M”的回答。例如:

int remove_occurences(int value_to_remove){
    int i = 0, total_elements = 0;
    for (; i < SIZE; i++)
         if (arr[i] != value_to_remove)
            arr[total_elements++] = arr[i];
    return total_elements;
}

为了更好地理解这个算法是如何工作的，让我们看看下面的例子会发生什么:

int arr[SIZE] = { 3, 5, 0, 9, 5 };

并删除“5”。第一次迭代:

if (3 != 5)

true，然后 arr[0] = 3; 和 total_elements++;

因为数组的第一个位置已经包含了 3，所以 arr[0] = 3; 看起来有点多余，但是，当一个查找要从数组中删除的值(即 5)。

第二次迭代:

if (5 != 5)

false，这里算法只是跳过并移动到数组的下一个位置。现在这样做的结果是变量 i 将继续向前移动，而变量 total_elements 将停止在包含要删除的元素的位置。所以在第三次迭代中:

if (0 != 5)

true，则 arr[total_elements] = arr[i]; 在本例中为 arr[1] = arr[2];，因此 arr[1] = 0;。

使用这种方法就不需要(当找到要删除的元素时)明确地进行元素的移动，即:

        for (j = i; j < (total_elements - 1) ;j++)
            arr[j] = arr[j+1];

移位是在遍历数组时隐式完成的。

关于您的代码的一些建议，必须考虑以下几点:

1. 变量SIZE不能递减；
2. 无论您是否删除元素，该数组在整个应用程序运行期间都将分配相同的空间。
3. 当一个人使用您的代码从数组中删除一个元素时，实际上并不是在删除该元素，而是将数组的所有元素向后移动，并确定该数组的最后一个位置将不被使用。

基于上述几点，我建议在分配数组后，您不应再使用常量 SIZE，因为它很容易失去同步并导致错误。相反，使用一个变量来跟踪数组中当前元素的数量。自然地，这将意味着更改您的代码，例如:

int remove_occurences(int size, int value_to_remove)

否则，您不能安全地多次调用函数remove_occurences，因为数组中的元素数量可能已经减少，但是变量SIZE 没有反射(reflect)这一点。