从Python中的字符串，删除重复，而无需使用adittional缓冲

问题描述：

我想在Python来解决这个问题：从Python中的字符串，删除重复，而无需使用adittional缓冲

given a string (without spacing), remove the duplicates without using an adittional buffer.

我有以下代码：

def removedup(st): 
temp = [] 
for i in range(len(st)): 
     if st[i] not in temp: 
       temp.append(st[i]) 
return temp

返回无重复的列表。

1-O（n^2）中的这段代码对不对？

2-我怎样才能做到这一点，而无需在Python中使用额外的缓冲区？（我的意思是不使用列表）。也许我可以使用一个字符串（不是列表），但不知道这是否会增加复杂性。另外，python中的字符串是不可变的，所以我不能做某种类型的索引来改变某些东西。（就像在C++或Java中）。

在Python中解决这个问题的最好方法是什么？我知道在这里有一些“看起来像”重复的问题，但我的问题是更多与Python有关的问题（无需额外的缓冲区即可解决此问题）。

谢谢！

答

1）是的。

2）好

return set(st)

..是迄今为止uniquify一个字符串（或任何可迭代），最简单的方法。我不知道你是否认为这是一个“额外的缓冲区”或不。一些额外的内存需要以任何方式分配给另一个对象，因为字符串像你说的那样是不可变的。

这当然不维持秩序，如果这是一个问题总是有超显而易见的：

from collections import OrderedDict 

return ''.join(OrderedDict.fromkeys(st))

你不需要'chain.from_iterable'在这里... –

@JonClements哦是的，不要猜测。 – roippi

是的，我读到了。 set的问题只是我正在使用内置的东西（太简单了！）。你如何将一个集合转换为一个字符串？（这似乎微不足道，但我知道如何！）有没有办法做到这一点，而不使用设置，连接或列表？如果没有，我的回答是正确的，对吧？ – Edwardo

答

0）显然，你有，因为正如你所提到的使用至少一个额外的缓冲， python字符串是不可变的，你至少需要以某种方式返回结果，对吧？所以内部至少已经使用了一个缓冲区（即使您使用相同的名称命名）。当然，你可以使用字符串作为缓冲区，他们可以做字符串+字符串或字符串+ =字符串，甚至字符串[：n-1] +字符串[n：]，但由于不可变性，每次创建一个新对象。

你可以使用一些其他的，可变的，可迭代的而不是字符串，所以它可以工作。

1）不，你的代码不是O（N ** 2）。在最坏的情况下（所有符号都是唯一的）是O（N * log（N）），在最好的情况下是O（N）（所有符号都只是一个符号）。

2）假设你使用的不是字符串的字符串列表，你可以做这样的事情：

def dup_remove(lst): 
    i = 0 
    n = len(lst) 
    while i < n: 
     if lst[i] in lst[:i]: 
      del lst[i] 
      n -= 1 
     else: 
      i += 1 
     return lst

它仍然是O（N *的log（n））在最坏的情况下，但它确实不要使用任何额外的缓冲区，这是你首先想要的。我认为实际的目的OrderedDict的解决方案应该是更优化的。

你能解释一下你的O（N log N）参数吗？日志N从哪里来？序列没有排序。 – DSM

你能解释一下为什么我的算法是O（N * log（N））？我不明白为什么......我不明白你为什么在你的代码中使用del ..每个del都可以是O（n）正确的？因为，你必须对我所有的元素... – Edwardo

好吧，你要经过原始字符串的长度是N，在每一步你通过额外的列表，直到找到当前的符号。在最糟糕的情况下，您只有唯一符号的字符串，因此： 1）您检查第一个符号，附加列表为空：1步。 2）您检查第二个符号，附加列表中有一个符号：2个步骤。 3）您检查第三个符号，附加列表中有两个符号：3个步骤。 .... N）您检查第N个符号，附加列表中有N-1个符号：N个步骤。所以我们对每个符号没有N个检查步骤，只有（1 + 2 + 3 + ... N）/ N。 –

答

另一种通过列表分片循环来实现的方法。

# O(n^2) 
for item in input_list[:]: 
    index = input_list.index(item) + 1 
    while index < len(input_list): 
     if input_list[index] == item: 
      del input_list[index] 
     index += 1

由于slice会创建一个副本，如果您真的想要一个没有任何内部缓冲区的解决方案，这将会起作用。

# O(n^2) 
i = 0 
while i < len(input_list): 
    j = i + 1 
    while j < len(input_list): 
     if input_list[j] == input_list[i]: 
      del input_list[j] 
      # Don't increment j here since the next item 
      # after the deleted one will move to index j 
     else: 
      j += 1 
    i += 1

答

1）我不确定。

2）一种非常有效的方法编码如下。请注意，我不使用任何额外的软件包。我甚至不使用列表，只是一个字符串！

def removeDuplicate (input): 

i = 0 
while i < len(input)-1: 
    j = i + 1 
    while j < len(input): 
     if input[j] == input[i]:     
      input_list = input_list[0:j] + input_list[j+1:]     
      # Don't increment j here since the next item 
      # after the deleted one will move to index j 
     else: 
      j += 1 
    i += 1 

return input

从Python中的字符串，删除重复，而无需使用adittional缓冲

相关推荐