Удаление повторяющихся символов в строке


У меня есть кусок кода на C, который удаляет все повторяющиеся символы в строке. Но я делаю это в две петли и хотели бы его оптимизировать одну петлю.

void removeDuplicates(char* ptr)
{
    int end = 1;
    int length = strlen(ptr);
    int current;
    int i;
    current = 1;

    for(end=1; end<length; end++)
    {
        for(i=0; i<end; i++)
        {
            if(ptr[end] == ptr[i])
            break;
        }

        if(i == end)
        {
            ptr[current] = ptr[i];
            current++;
        }
    }

    ptr[current] = 0;
}

int main(int argc, char** argv)
{
    char str[256] = {0,};
    gets(str);
    removeDuplicates(str);
    printf("%s\n", str);
    return 1;
}


4878
5
задан 18 октября 2011 в 09:10 Источник Поделиться
Комментарии
3 ответа

Удалить дубликаты: (переписать код муравьиный так это читается).

#include <stdio.h>

void removeDuplicates(char* ptr);

void removeDuplicates(char* ptr)
{
char seen[UCHAR_MAX+1] = {0};

//
// Smallest data type is a char (unless you want to bit
// twiddle, and that has been shown to be not worth it
// see the complaints about std::vector<bool> in C++).
// 256 bytes is not much.
//
// By using char as they type it prevents all the complex
// multiplication/division an bit twiddling that Ant was doing.

unsigned char* source = (unsigned char*)ptr;
unsigned char* dest = (unsigned char*)ptr;
unsigned char next;

do
{
next = *source; // Get next character.
if (!seen[next]) // Only enter the `if block` if we have not seen it.
{
seen[next] = 1; // Mark it as seen
*dest = next; // Move it to destination.
// Note: source will change faster than dest when we
// start seeing dupes, this acts as the copy back
// over the duplicates.
++dest;
}
++source;
}
while (next != '\0'); // Once we have copied the null terminator quit.
}

7
ответ дан 18 октября 2011 в 03:10 Источник Поделиться

Я считаю, что это должен получиться быстрее и эффективнее:

#include <stdio.h>

void removeDuplicates(char* ptr);

void removeDuplicates(char* ptr) {
int seen[(sizeof(char) << 8) / (sizeof(int) * 8)] = {0,};

char* source = ptr;
char* dest = ptr;

while (*source != '\0') {

int destIndex = (*source) / (sizeof(int) * 8);
int destBit = 1 << (*source) % (sizeof(int) * 8);

if (!(seen[destIndex] & destBit)) {
*dest = *source;
++dest;

seen[destIndex] |= destBit;
}

++source;
}

*dest = '\0';
}

int main (int argc, const char * argv[])
{
char str[256] = {0,};
gets(str);
removeDuplicates(str);
printf("%s\n", str);
return 0;
}

Он использует массив Ints как массив логических значений, каждое из которых определяет, является ли символ был замечен. Это исключает функция strlen() вызов (который перебирает все строки) и заменяет его нулевым чеком. Он использует два указателя на строки, источник и приемник, которые отслеживают текущую читал местоположения (итерации исходной строки) и текущей записи (место назначения для копирования следующего номера-повторяющийся характер).

2
ответ дан 18 октября 2011 в 02:10 Источник Поделиться

Если вы платите за время, вы можете потратить некоторую память и использовать массив длины размером sizeof(тип char) - назовем это видел -- инициализируется нулями.

В петле тебе несколько вещей:


  1. если видели счетчик больше нуля, приращение является смещение переменной (величина этого смещения равна сколько дубликатов всех персонажей до сих пор не найдено)

  2. скопируйте текущий символ в новое положение, смещение символов за, если он ранее не видел, что значит, если видишь current_char] равен нулю (возможно, только если смещение не равно нулю, в противном случае "из" и "в" позиции те же)

  3. Инкремент видел[current_char] в конце цикла

Обратите внимание, что current_char действительно значение символа, а не Индекс символа в строке ввода.

0
ответ дан 18 октября 2011 в 12:10 Источник Поделиться