本文共 1403 字,大约阅读时间需要 4 分钟。
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
示例 2:给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
说明:给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
解法一:
class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ if not nums: # 判断是否为空数组 return 0 start = 0 # 新数组下标 for i in range(1, len(nums)): if nums[i] != nums[start]: start += 1 nums[start] = nums[i] return start + 1if __name__ == '__main__': a = Solution() result = a.removeDuplicates([1,2,2,3,3,3,4]) print(result)
结果为4
解法二:
class Solution: def removeDuplicates(self, nums): """ :type nums: List[int] pe: int """ i=0 while i
以下是Java版本:
/** * 移除有序数组中的重复元素: * 给定一个排序的数组,将数组中的重复元素去掉,相同的只保留一个,并且返回数组新的元素个数, * 不要创建一个新的数组来保存结果。 * * 做法是维护两个指针,一个保留当前有效元素的长度,一个从前往后扫,然后跳过那些重复的元素。 * 因为数组是有序的,所以重复元素一定相邻,不需要额外记录。 * 时间复杂度是O(n),空间复杂度O(1)。*/public class RemoveDuplicates { public int removeDuplicates(int[] nums) { if(nums == null || nums.length==0) return 0; int index = 1; for(int i=1;i
转载地址:http://usuvi.baihongyu.com/