Удаление дубликатов в строке в Python

Question

Каков эффективный алгоритм удаления всех дубликатов в строке?

Например: aaaabbbccdbdbcd

Требуемый результат: abcd

Answer 1

Вы используете хеш-таблицу для хранения открытых ключей (доступ O (1)), а затем перебираете массив. Если персонаж находится в хеш-таблице, откажитесь от него. Если это не так, добавьте его в хеш-таблицу и строку результата.

В целом: O (n) время (и пространство).

Наивным решением является поиск символа - строки результата при обработке каждого из них. Это O (n ² ).

Answer 2

Это тесно связано с вопросом: Обнаружение повторения с бесконечным вводом .

Подход с хэш-таблицей может быть неоптимальным в зависимости от вашего ввода. Хеш-таблицы имеют определенное количество служебных данных (корзины, объекты ввода). Это огромные накладные расходы по сравнению с фактически сохраненным символом. (Если целевой средой является Java, это еще хуже, поскольку HashMap имеет тип Map<Character,?>.) Время выполнения худшего случая для доступа к Hashtable - O (n) из-за коллизий.

Вам нужно только 8kb также представлять все 2-байтовые символы Юникода в виде простого BitSet . Это может быть оптимизировано, если ваш входной набор символов более ограничен или используется сжатый набор битов (если у вас есть разреженный набор битов). Производительность во время выполнения будет благоприятной для BitSet, это O (1).

Answer 3

In Python

>>> ''.join(set("aaaabbbccdbdbcd"))
'acbd'

Если необходимо сохранить заказ

>>> q="aaaabbbccdbdbcd"                    # this one is not
>>> ''.join(sorted(set(q),key=q.index))    # so efficient
'abcd'

или

>>> S=set()
>>> res=""
>>> for c in "aaaabbbccdbdbcd":
...  if c not in S:
...   res+=c
...   S.add(c)
... 
>>> res
'abcd'

или

>>> S=set()
>>> L=[]
>>> for c in "aaaabbbccdbdbcd":
...  if c not in S:
...   L.append(c)
...   S.add(c)
... 
>>> ''.join(L)
'abcd'

In python3.1

>>> from collections import OrderedDict
>>> ''.join(list(OrderedDict((c,0) for c in "aaaabbbccdbdbcd").keys()))
'abcd'

Answer 4

Вы можете сделать это в O (n), только если вы используете HashTable. Код указан ниже Обратите внимание - предполагается, что количество возможных символов во входной строке 256

void removeDuplicates(char *str)
{
 int len = strlen(str); //Gets the length of the String
 int count[256] = {0};  //initializes all elements as zero
 int i;
     for(i=0;i<len;i++)
     {
        count[str[i]]++;  
        if(count[str[i]] == 1)
          printf("%c",str[i]);                  
     }     
}

Answer 5

Алгоритм PHP - O (n):

function remove_duplicate_chars($str) {
    if (2 > $len = strlen($str)) {
        return $str;
    }
    $flags = array_fill(0,256,false);
    $flags[ord($str[0])]=true;
    $j = 1;
    for ($i=1; $i<$len; $i++) {
        $ord = ord($str[$i]);
        if (!$flags[$ord]) {
            $str[$j] = $str[$i];
            $j++;
            $flags[$ord] = true;
        }
    }
    if ($j<$i) { //if duplicates removed
        $str = substr($str,0,$j);
    }
    return $str;
}

echo remove_duplicate_chars('aaaabbbccdbdbcd'); // result: 'abcd'

Answer 6

Сохраните массив из 256 «видимых» логических значений, по одному на каждый возможный символ. Поток вашей строки. Если вы раньше не видели этот символ, выведите его и установите для этого символа флаг «Видели».

Answer 7

#include <iostream>
#include<string>
using namespace std;
#define MAX_SIZE 256

int main()
{
    bool arr[MAX_SIZE] = {false};

    string s;
    cin>>s;
    int k = 0;

    for(int i = 0; i < s.length(); i++)
    {
        while(arr[s[i]] == true && i < s.length())
        {
            i++;
        }
        if(i < s.length())
        {
            s[k]    = s[i];
            arr[s[k]] = true;
            k++;
        }
    }
    s.resize(k);

    cout << s<< endl; 

    return 0;
}

Answer 8

int main()    
{    
    std::string s = "aaacabbbccdbdbcd";

    std::set<char> set1;
    set1.insert(s.begin(), s.end());

    for(set<char>::iterator it = set1.begin(); it!= set1.end(); ++it)
    std::cout << *it;

    return 0;
}

std::set takes O(log n) to insert 

Answer 9

получить список первых 26 простых чисел .. Теперь вы можете отобразить каждый символ (a, b, c, d и т. Д.) На каждое простое число .. (в алфавитном порядке сказать a = 2, b = 3, c = 5 и т. Д.) Или в зависимости от относительного обилия символов, как чаще всего использованная буква с меньшим простым числом, скажем, e = 2, r = 3, a = 5 и т. д.) ... сохранить это отображение в целочисленном массиве int prime [26] ..

перебрать все символы строки

i=0;
int product = 1;
while(char[i] != null){
   if(product % prime[i] == 0)
      the character is already present delete it
   else
      product = product*prime[i];
}

этот алгоритм будет работать за O (n) времени .. с O (1) пространством Это будет хорошо работать, когда число отдельных символов меньше в строке ... другой мудрый продукт превысит диапазон "int", и мы должны правильно обработать этот случай

Answer 10

import java.util.HashSet;

public class RemoveDup {

    public static String Duplicate()
    {
        HashSet h = new HashSet();
        String value = new String("aaaabbbccdbdbcd");
        String finalString = new String();
        int stringLength = value.length();
        for (int i=0;i<=stringLength-1;i++)
        {
            if(h.add(value.charAt(i)))
            {
                finalString = finalString + (value.charAt(i));
            }


        }
        return finalString;

    }
public static void main(String[] args) {


        System.out.println(Duplicate());
    }
}