0

この問題を Python で解決したい:

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に関連しています(追加のバッファーなしでこれを解決します)。

ありがとうございました！

4

4 に答える 4

5

1) はい。

2) まあ

return set(st)

..これは、文字列 (またはイテラブル) を一意化する最も簡単な方法です。これを「追加のバッファー」と見なすかどうかはわかりません。あなたが言うように、文字列は不変であるため、どのような方法でも別のオブジェクトに追加のメモリを割り当てる必要があります。

もちろん、これは順序を保持しません。それが問題である場合は、常に非常に明白なことがあります。

from collections import OrderedDict

return ''.join(OrderedDict.fromkeys(st))
于 2013-10-12T22:19:00.610 に答える
1

0) 前述のように、python 文字列は不変であり、少なくとも何らかの方法で結果を返す必要があるため、少なくとも 1 つの追加バッファーを使用する必要があるようです。そのため、内部的に少なくとも 1 つのバッファーが既に使用されています (同じ名前で名前を付けたとしても)。

もちろん、文字列をバッファとして使用できます。文字列 + 文字列または文字列 += 文字列、さらには文字列 [:n-1] + 文字列 [n:] を実行できますが、不変性のため、内部的にそれぞれ新しいオブジェクトが作成されます。時間。

文字列の代わりに、変更可能で反復可能な他のものを使用できるため、機能します。

1) いいえ、あなたのコードは O(N**2) ではありません。最悪のシナリオ (すべてのシンボルが一意) では O(N*log(N)) であり、最良のシナリオ (すべてのシンボルは 1 つのシンボル) では 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 を使用した実用的なソリューションはより最適であると思います。

于 2013-10-13T00:19:20.030 に答える
0

リストスライスループを介してそれを行う別の方法。

# 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

スライスはコピーを作成するため、内部バッファーのないソリューションが本当に必要な場合は、これで十分です。

# 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
于 2014-04-28T06:37:08.297 に答える