给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。\n\n不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 o(1) 额外空间的
时间: 2023-05-31 15:20:19 浏览: 112
### 回答1:
要求你一个程序数组 nums ,请你原地删除重复出现的元素,使每个元素只出现一次,每个元素只出现一次后返回删除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并使用 O(1) 额外空间。
### 回答2:
题目意思
给定一个有序数组nums,要求在原地删除其中重复的元素,使得每个元素只出现一次,并返回删除后的新长度。不允许使用额外的数组空间,并且需要使用O(1)的额外空间。
思路分析
由于原数组是有序的,我们只需要比较相邻的元素是否相等。如果相等,则将后面的元素删除,即将后面元素覆盖到当前位置。如果不相等,则继续比较下一个元素。最后返回新数组的长度即可。
代码实现
下面是Python3代码实现:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
i = 0
for j in range(1, n):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1
时间复杂度为O(n),空间复杂度为O(1)。
### 回答3:
题目描述:
给你一个有序数组 nums ,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。
目标是在原地修改输入数组并在使用 O(1) 额外空间的情况下完成此操作。
解题思路:
因为数组是有序的,所以重复的元素一定相邻。我们可以使用双指针解题,一个指针 (i) 指向当前判断的元素,一个指针 (j) 指向不重复元素的最后一位。i从1开始遍历数组,如果nums[i]和nums[j]不同,那么我们就将nums[i]放到nums[j+1]的位置上。因为我们需要在原地修改数组,所以不能新建数组,需要直接修改nums数组。最后,j指向的位置就是不重复数组的末尾,所以数组长度为 j+1。
参考代码:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
j = 0
for i in range(1, len(nums)):
if nums[i] != nums[j]:
j += 1
nums[j] = nums[i]
return j + 1
复杂度分析:
时间复杂度 O(n) : 数组的长度为 n,只遍历一遍数组。
空间复杂度 O(1) : 只使用两个额外指针,没有使用额外空间。
阅读全文