Python 中从已经排序的数组中移除重复元素

假设我们有一个已排序的列表 A。我们需要返回移除所有重复项后数组的长度。我们必须在 O(1) 的额外空间内执行此操作。因此，我们必须在原地操作。

例如，假设 A = [1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6]，则输出为 6，因为有六个不同的元素。

要解决此问题，请遵循以下步骤 -

  • 如果列表为空，则返回 0
  • 否则，最初 take prev = A 的第一个元素。定义 length = 0
  • 对于 i := 1 到 n-1，执行
    • 如果 A[i] 与 prev 不同，则
      • length := length + 1
      • prev := A[i]
  • 返回 length

让我们看一下实现，以便更好地理解

示例（Python）

 在线演示

class Solution(object):
   def removeDuplicates(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      if len(nums) == 0:
         return 0
      length = 1
      previous = nums[0]
      index = 1
      for i in range(1,len(nums)):
         if nums[i] != previous:
            length += 1
            previous = nums[i]
            nums[index] = nums[i]
            index+=1
      return length
input_list = [1,1,2,2,2,3,3,3,3,4,5,5,5,6]
ob1 = Solution()
print(ob1.removeDuplicates(input_list))

输入

[1,1,2,2,2,3,3,3,3,4,5,5,5,6]

输出

6

更新于：2020 年 4 月 28 日

4K+ 浏览量

启动你的 职业生涯

通过完成课程获得认证

开始使用
广告