从列表中删除相邻的重复元素

Question

谷歌 Python 类 |清单练习 -

给定一个数字列表，返回一个列表，其中所有相邻的 == 元素都已缩减为单个元素，因此 [1, 2, 2, 3] 返回 [1, 2, 3]。您可以创建一个新列表或修改传入的列表。

我使用新列表的解决方案是 -

 def remove_adjacent(nums):
  a = []
  for item in nums:
    if len(a):
      if a[-1] != item:
        a.append(item)
    else: a.append(item)
  return a

这个问题甚至表明可以通过修改传入的列表来完成。但是，python 文档警告不要在使用 for 循环迭代列表时修改元素。

我想知道除了遍历列表之外我还能尝试什么来完成这项工作。我不是在寻找解决方案，而是在寻找可以引导我走向正确方向的提示。

更新

-用建议的改进更新了上面的代码。

- 使用建议的提示在 while 循环中尝试以下操作 -

 def remove_adjacent(nums):
  i = 1
  while i < len(nums):
    if nums[i] == nums[i-1]:
      nums.pop(i)
      i -= 1
    i += 1
  return nums

原文由 Vaibhav Bajpai 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

使用生成器迭代列表的元素，并且 yield 只有在它发生变化时才生成一个新元素。

itertools.groupby 正是这样做的。

如果您遍历一个副本，您可以修改传入的列表：

 for elt in theList[ : ]:
    ...

原文由 Katriel 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

这是传统的方法，在原地删除相邻的重复项，同时向后遍历列表：

 Python 1.5.2 (#0, Apr 13 1999, 10:51:12) [MSC 32 bit (Intel)] on win32
Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
>>> def dedupe_adjacent(alist):
...     for i in xrange(len(alist) - 1, 0, -1):
...         if alist[i] == alist[i-1]:
...             del alist[i]
...
>>> data = [1,2,2,3,2,2,4]; dedupe_adjacent(data); print data
[1, 2, 3, 2, 4]
>>> data = []; dedupe_adjacent(data); print data
[]
>>> data = [2]; dedupe_adjacent(data); print data
[2]
>>> data = [2,2]; dedupe_adjacent(data); print data
[2]
>>> data = [2,3]; dedupe_adjacent(data); print data
[2, 3]
>>> data = [2,2,2,2,2]; dedupe_adjacent(data); print data
[2]
>>>

更新： 如果你想要一个生成器但是（没有 itertools.groupby 或（你可以输入比你阅读它的文档和理解它的默认行为更快的速度）），这里有一个六行的工作：

 Python 2.3.5 (#62, Feb  8 2005, 16:23:02) [MSC v.1200 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> def dedupe_adjacent(iterable):
...     prev = object()
...     for item in iterable:
...         if item != prev:
...             prev = item
...             yield item
...
>>> data = [1,2,2,3,2,2,4]; print list(dedupe_adjacent(data))
[1, 2, 3, 2, 4]
>>>

更新 2： 关于巴洛克风格 itertools.groupby() 和极简主义 object() …

要从 itertools.groupby() 中获得 dedupe_adjacent 效果，您需要围绕它包装一个列表理解以丢弃不需要的石斑鱼：

 >>> [k for k, g in itertools.groupby([1,2,2,3,2,2,4])]
[1, 2, 3, 2, 4]
>>>

…或与 itertools.imap 和/或 operators.itemgetter ，如另一个答案所示。

object 实例的预期行为是它们与任何类的任何其他实例（包括 object 本身）相比都不相等。因此，它们作为哨兵非常有用。

 >>> object() == object()
False

值得注意的是 itertools.groupby 的 Python 参考代码 使用 object() 作为哨兵：

 self.tgtkey = self.currkey = self.currvalue = object()

并且该代码在您运行时会做正确的事情：

 >>> data = [object(), object()]
>>> data
[<object object at 0x00BBF098>, <object object at 0x00BBF050>]
>>> [k for k, g in groupby(data)]
[<object object at 0x00BBF098>, <object object at 0x00BBF050>]

更新三： 正向指数原位操作说明

OP的修订代码：

 def remove_adjacent(nums):
  i = 1
  while i < len(nums):
    if nums[i] == nums[i-1]:
      nums.pop(i)
      i -= 1
    i += 1
  return nums

最好写成：

 def remove_adjacent(seq): # works on any sequence, not just on numbers
  i = 1
  n = len(seq)
  while i < n: # avoid calling len(seq) each time around
    if seq[i] == seq[i-1]:
      del seq[i]
      # value returned by seq.pop(i) is ignored; slower than del seq[i]
      n -= 1
    else:
      i += 1
  #### return seq #### don't do this
  # function acts in situ; should follow convention and return None

原文由 John Machin 发布，翻译遵循 CC BY-SA 2.5 许可协议