时间戳

首页 > 解决方案 > 从C中的数组中删除给定数字的所有出现

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

问题描述

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

你有一个有点大小的整数数组 - 即 arr[SIZE]。编写一个函数，从数组中删除所有出现的给定数字 x

我已经编写了这个函数（如下），它适用于数字为 1 且仅出现但不适用于多次的情况，我正在努力为最后一种情况（多次出现）寻找突破口。我的想法是：在匹配的情况下 - 左移一个索引匹配右侧的所有元素并返回用户一个“新”大小。

对于下面的示例：{ 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;
}

谢谢

标签： arraysc

解决方案

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

{ 3, 0, 5, 5, 6 }

您将删除第一个5

{ 3, 0, x, 5, 6 }

移动数组的元素：

{ 3, 0, 5, 6, x}

但现在你应该从这个i位置重新开始 noti+1.否则，你将跳过当前的 second 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)），正如您可以在此处和“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并未反映这一点。

推荐阅读