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

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

---

请不要使用<>，正确的表示法是!=。使用if a，而不是if len(a) <> 0。 - Katriel

@Aran-Fey 我个人认为，这个问题和重复的目标都应该被关闭，作为删除具有连续重复项的元素的重复。 - Georgy

Answer 1

这里介绍一种传统的方法，即在向后遍历列表时，在原地删除相邻重复项：

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() 中获取去重相邻项的效果，您需要在其周围包装一个列表推导式，以丢弃不需要的分组器：

>>> [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>]

更新3: 关于前向索引原地操作的说明

原帖作者修改后的代码：

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

---

Python 1.5.2。你在FreeDOS上运行它吗？ - aaronasterling

@aaronasterling: 不，只有在Windows XP上偶尔会出现，比如当我看到有人使用itertools.groupby等去完成一些简单的事情时。;-) - John Machin

@John Machin。我非常喜欢你的算法。等我的投票恢复后，我会在一分钟内给你点赞。 - aaronasterling

这种做法有点巧妙，做prev = object( )并希望object( )不是可迭代对象中的第一项！更正确的做法是，虽然稍微不太优雅，但需要做iterable = iter(iterable)（确保它是一个迭代器），然后再做prev = next(iterable)。 - Katriel

@katrielalex：我所希望的是object()实例继续保持“无特征”；-) 在Python 2.2及以后的版本中，检查object() == object()和dir(object())的结果。 - John Machin

哦，我不知道那个。我撤回之前的声明！ - Katriel

Answer 2

使用生成器遍历列表元素，仅在其有变化时yield生成新的元素。

itertools.groupby正好实现了这一功能。

如果你对一个拷贝进行迭代，就可以修改传入的列表：

for elt in theList[ : ]:
    ...

- Katriel

---

当迭代复制品时，我不是修改原件而是传入的实际列表吗？ - Vaibhav Bajpai

是的，您必须显式地引用原始列表，例如使用元素的索引。 - Katriel

我不同意这个观点。即使在迭代副本时从原始列表中删除元素，也可能会犯许多错误。我认为修改正在迭代的列表中的元素的最佳方法是反向迭代列表，并按索引修改元素。 - Paul Seeb

答案是：list(x.next() for i, x in groupby(my_list))。 - est

list(i for i, x in groupby(my_list)) - anonymous

Answer 3

这里再展示一种不需要索引的单行代码：

def remove_adjacent(nums):
     return [a for a,b in zip(nums, nums[1:]+[not nums[-1]]) if a != b]

not部分将最后一个值作为结果放入result中，因此只有a会被添加到result中。

- Tony Veijalainen

Answer 4

像往常一样，我在这里宣传Python itertools文档中令人印象深刻的配方。

你需要的是函数unique_justseen：

from itertools import imap, groupby
from operator import itemgetter

def unique_justseen(iterable, key=None):
    "List unique elements, preserving order. Remember only the element just seen."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return imap(next, imap(itemgetter(1), groupby(iterable, key)))

list(unique_justseen([1,2,2,3])) # [1, 2, 3]

- Muhammad Alkarouri

Answer 5

好的，katrielalex关于itertools的说法是正确的，但是问题的发起者似乎更感兴趣（或者应该更感兴趣！）于学习如何操作内置数据结构的基础知识。至于在原地操作列表，确实需要一些思考，但是我的建议是阅读文档中的这个部分，尝试一些列表方法（提示：list.pop()、list.remove()，以及学习有关切片的所有内容）。请注意，发布的代码可以简化（但是您应该添加错误条件的处理）：

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

- chryss

---

有趣的发现，nums[0]返回一个整数，而nums[:1]返回一个只有一个元素的列表！谢谢！ - Vaibhav Bajpai

通过切片的魔法，如果nums为空列表，则nums[:1]将返回一个空列表，从而在提供空列表作为输入的情况下给出正确的行为。相比之下，如果nums为空列表，nums[0]会引发KeyError。 - PaulMcG

Answer 6

这是来自 Google 的非常优美的解决方案（来源在此：https://developers.google.com/edu/python/exercises/basic）：

def remove_adjacent(nums):
    result = []
    for num in nums:
        if len(result) == 0 or num != result[-1]:
            result.append(num)
    return result

- dainys

Answer 7

试试这个：

def remove_adjacent(nums):
  result = []
  if len(nums) > 0:
    result = [nums[0]]
    for i in range(len(nums)-1):
        if nums[i] != nums[i+1]:
            result.append(nums[i+1])

  return result

- Rajesh

Answer 8

你可以使用列表推导式。例如，像这样的代码应该可以完成任务：

def remove_adjacent(L):
  return [elem for i, elem in enumerate(L) if i == 0 or L[i-1] != elem]

或者：

def remove_adjacent(L):
  return [L[i] for i in xrange(len(L)) if i == 0 or L[i-1] != L[i]]

- Winston

Answer 9

"itertools.groupby"是更优秀的，但也有其他选项。保留html，不进行解释。

reduce(lambda x, y: x + [y] if x[-1] != y else x, seq[1:], seq[0:1])

e.g.

>>> seq = [[1,1], [2,2], [3,3], [3,3], [2,2], [2,2], [1,1]]
>>> print reduce(lambda x, y: x + [y] if x[-1] != y else x, seq[1:], seq[0:1])
[[1, 1], [2, 2], [3, 3], [2, 2], [1, 1]]

当从函数式语言转来时，这种事情通常是用fold完成的，因此使用reduce会感觉更自然。

- ely

Answer 10

另一种方法。欢迎评论。

def remove_adjacent(nums):
    '''modifies the list passed in'''
    l, r = 0, 1
    while r < len(nums):
        if nums[l] == nums[r]:
            r += 1
        else:
            l += 1
            nums[l] = nums[r]
            r += 1
    del nums[l+1:]

- AndJM