本文最后更新于 2024-07-31，文章内容可能已经过时。

题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。

  • 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

 

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

 

提示：

  • 0 <= nums.length <= 100

  • 0 <= nums[i] <= 50

  • 0 <= val <= 100

答案代码

"""
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
"""


class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        while val in nums:
            nums.remove(val)
        return len(nums)


if __name__ == '__main__':
    s = Solution()
    print(s.removeElement([3, 2, 2, 3], 3))

if __name__ == '__main__':
    s = Solution()
    print(s.removeElement([0, 1, 2, 2, 3, 0, 4, 2], 2))

结果分析

时间复杂度：

空间复杂度：

在这段代码中，使用了一个 while 循环来判断指定的值 val 是否存在于数组 nums 中。如果 val 存在于nums 中，就使用 remove 方法将其移除。这个循环会一直执行，直到 val 不再存在于 nums 中。因此，这个循环的执行次数取决于 val 在nums 中出现的次数。在最坏的情况下，val 在 nums 中出现的次数等于 nums 的长度，因此循环的执行次数为 n，其中 n 是 nums 的长度。

由于 remove 方法的平均时间复杂度为 O(n)（因为需要遍历整个数组来找到要移除的元素），所以这个算法的平均时间复杂度为 O(n^2)。但是，如果 val 在 nums 中出现的次数较少，那么算法的实际执行时间会更短。

在空间复杂度方面，这段代码只使用了常数级别的额外空间。这是因为它只使用了一个变量 val 和一个列表 nums，它们所需的存储空间与 nums 的大小无关