小企业网站建设价格南京建站平台

如何删除数组中的某个元素？

例：给你一个数组 nums 和一个值 val，你需要移除所有数值等于 val 的元素，并返回移除后数组的新长度。

三种方法

1.元素前移（时间复杂度：O(N^2)，空间复杂度：O(1)）

遍历数组，当遇到需要删除的元素时，则将其后面的元素全部前移一个空间，覆盖当前需要删除的元素。前移后下标不变，需要再次判断当前位置的元素是否为要删除元素。

int removeElement(int* nums, int numsSize, int val)
{int newnumsSize = numsSize;for (int i = 0; i < numsSize; i++){if (nums[i] == val){newnumsSize--;for (int j = i; j < numsSize - 1; j++)nums[j] = nums[j + 1];i--;//后一元素前移后该元素仍要判断是否为val}}return newnumsSize;
}int main()
{int nums[] = { 3,2,6,6,6,6,7,8,9 };int newnumsSize = removeElement(nums, 9, 6);for (int i = 0; i < newnumsSize; i++)printf("%d ", nums[i]);return 0;
}

2.快慢指针（额外数组，空间换时间）（时间复杂度：O(N)，空间复杂度O(N)）

创建一个快指针、一个慢指针和一个数组。通过快指针遍历原数组，只要遇到的元素不等于val，那么就将该元素通过慢指针赋值到新数组中。这样快指针遍历完成后，新数组中的元素就是不包含val的元素，再将新数组的元素赋值到原数组中，即可完成删除val。

int removeElement(int* nums, int numsSize, int val)
{int* newnums = (int*)malloc(sizeof(int) * numsSize);//建立新数组int fast = 0;int slow = 0;for (fast = 0; fast < numsSize; fast++){if (nums[fast] != val){newnums[slow] = nums[fast];slow++;}}for (int i = 0; i < slow; i++)//将新数组赋值到原数组中{nums[i] = newnums[i];}return slow;
}int main()//测试
{int nums[] = { 3,6,6,6,6,7,8,9,10,11 };int newnumsSize = removeElement(nums, 10, 6);for (int i = 0; i < newnumsSize; i++){printf("%d ", nums[i]);}return 0;
}

3.快慢指针（非额外数组）（时间复杂度：O(N)，空间复杂度O(1)）

创建一个快指针和一个慢指针，不再创建新的数组，而是直接在原数组中进行元素的赋值拷贝。（本质其实和额外数组相同，只是将不等于val的元素拷贝到原数组中，这样val元素就会被覆盖或者在数组新长度的界外）通过快指针遍历数组， 如果快指针遍历遇到不等于 val 的元素，则将该元素赋值到慢指针指向的位置，且慢指针位置后移。这样遍历完成后，数组中的val元素就会被“删除”

int removeElement(int* nums, int numsSize, int val)
{int fast = 0;int slow = 0;for (fast = 0; fast < numsSize; fast++){if (nums[fast] != val){nums[slow] = nums[fast];slow++;}  }return slow;
}