Ваш алгоритм в основном такой.
- Посмотрите на букву.
- Отметьте, если какая-либо следующая буква отличается.
- Если это так, замените исходную буквус *
Если мы напишем ваш код с петлями for, код станет более понятным.И если мы добавим несколько отладочных отпечатков, то увидим проблему.
void replace( char *A ) {
for(int i = 0; i<N; i++) {
int flag = 0;
printf("i = %d, A[i] = %c\n", i, A[i]);
for(int j = 0; flag==0 && j<N; j++) {
printf(" j = %d, A[j] = %c\n", j, A[j]);
if( A[i]!=A[j] ) {
flag=1;
}
}
if( flag==1 ) {
A[i]='*';
}
}
}
Запуск этого ...
$ ./test
i = 0, A[i] = A
j = 0, A[j] = A
j = 1, A[j] = B
i = 1, A[i] = B
j = 0, A[j] = *
i = 2, A[i] = C
j = 0, A[j] = *
i = 3, A[i] = e
j = 0, A[j] = *
i = 4, A[i] = A
j = 0, A[j] = *
i = 5, A[i] = C
j = 0, A[j] = *
i = 6, A[i] = f
j = 0, A[j] = *
i = 7, A[i] = B
j = 0, A[j] = *
********
Первая проблема - вместо просмотра следующих букв, вывсегда заново сканируешь всю строку.Буква всегда видит себя.
Во-вторых, вы помечаете буквы, которые отличаются, A[i] != A[j].Вы ищете дубликаты, чтобы получить одинаковые буквы, A[i] == A[j].Если все символы не уникальны, всегда будет дубликат.
Когда мы исправим эти две проблемы, начнем внутренний цикл с j = i+ и отметим, если A[i] == A[j], мы получим лучший результат.
$ ./test
i = 0, A[i] = A
j = 1, A[j] = B
j = 2, A[j] = C
j = 3, A[j] = e
j = 4, A[j] = A
i = 1, A[i] = B
j = 2, A[j] = C
j = 3, A[j] = e
j = 4, A[j] = A
j = 5, A[j] = C
j = 6, A[j] = f
j = 7, A[j] = B
i = 2, A[i] = C
j = 3, A[j] = e
j = 4, A[j] = A
j = 5, A[j] = C
i = 3, A[i] = e
j = 4, A[j] = A
j = 5, A[j] = C
j = 6, A[j] = f
j = 7, A[j] = B
i = 4, A[i] = A
j = 5, A[j] = C
j = 6, A[j] = f
j = 7, A[j] = B
i = 5, A[i] = C
j = 6, A[j] = f
j = 7, A[j] = B
i = 6, A[i] = f
j = 7, A[j] = B
i = 7, A[i] = B
***eACfB
Это не сработает.Даже если мы каждый раз заново сканируем всю строку, стараясь пропустить текущую букву A[i], алгоритм разрушителен.Последний А не увидит более ранний А, потому что они будут превращены в *.
Есть лучший способ.
Циклы в циклах, как правило, плохие новости, потому что они оченьнеэффективно очень быстро.Это решение O (N ^ 2), означающее, что, поскольку длина строки удваивается, она должна выполнять работу в 4 раза больше.
Вместо этого мы можем сделать это за два прохода.Сначала посчитайте количество каждого символа в строке.В нем всего 255 символов, поэтому мы можем хранить его всего в 255 байтах.(Обратите внимание, что если строка содержит более 255 дубликатов одного и того же символа, это будет переполнено. Чтобы быть в безопасности, вы просто должны хранить 0, 1 или 2, представляющие невидимые, уникальные и дубликаты. Но для простоты я просто увеличу.)
unsigned short counts[255] = {0};
for(size_t i = 0; i < size; i++) {
size_t this_char = (size_t)A[i];
counts[this_char]++;
}
Затем выполните второй проход во втором цикле, чтобы выполнить преобразование на основе счетчиков.
for(size_t i = 0; i < size; i++ ) {
size_t this_char = (size_t)A[i];
if( counts[this_char] > 1 ) {
A[i] = '*';
}
}
Это аккуратно разделяет задачу на две части: подсчитайте символы, а затем разобраться с более сложным кодом замены.Это упрощает проблему, разделяя ее.
Это также более эффективно.Нам нужно только дважды просмотреть строку, O (2N) намного лучше, чем O (N ^ 2).И мы используем только небольшой и фиксированный объем стековой памяти.
Но это еще не правильно.Он выполняет первую часть, заменяет дублированные буквы на *, но не на вторую, только заменяет первую.
***e**f*
Теперь это не простая замена 1-к-1,Нам нужно «сдвинуть» следующие буквы.Есть несколько способов сделать это, мы могли бы выделить память для новой строки, создать эту строку и скопировать ее в существующую память, но это расточительно.Есть лучший способ.
Мы можем написать на месте.Это потребует отслеживания двух позиций в строке одновременно, где мы читаем и где пишем.Это работает, потому что мы никогда не пишем больше, чем читаем, поэтому писатель всегда будет рядом с читателем или позади него.
С индексами легко обойтись.Проще сделать это с помощью указателей, чтобы отслеживать, где мы находимся в строке, поэтому давайте переключимся на указатели.Это также означает, что нам больше не нужно знать размер строки, мы просто увеличиваем указатель, пока не достигнем нулевого байта.
void replace(char *A) {
unsigned short counts[255] = {0};
for( char *reader = A; *reader != '\0'; reader++ ) {
size_t this_char = (size_t)*reader;
counts[this_char]++;
}
for( char *reader = A; *reader != '\0'; reader++ ) {
size_t this_char = (size_t)*reader;
if( counts[this_char] > 1 ) {
*reader = '*';
}
}
}
Следующий шаг - отделить наше чтение от записи.Первый цикл остается прежним.Во второй цикл мы добавим указатель writer, чтобы отслеживать, где в строке мы пишем.
char *writer = A;
for( char *reader = A; *reader != '\0'; reader++ ) {
size_t this_char = (size_t)*reader;
if( counts[this_char] > 1 ) {
*writer = '*';
writer++;
}
else {
*writer = *reader;
writer++;
}
}
Обратите внимание, что writer продвигается только тогда, когда он записывается.В приведенном выше коде он всегда записывается в, и обычно вы помещаете writer++ вне if / else.Но следующий шаг это меняет.
Следующий шаг - отследить, какие буквы уже были заменены, и заменять только в первый раз, когда мы его увидим.Это означает, что другой массив отслеживания.Также как counts у нас есть replaced.
unsigned short replaced[255] = {0};
char *writer = A;
for( char *reader = A; *reader != '\0'; reader++ ) {
size_t this_char = (size_t)*reader;
// It's a duplicate and it hasn't been replaced yet
if( counts[this_char] > 1 && !replaced[this_char] ) {
// Replace it. Note that we replaced it. Advance the writer position.
*writer = '*';
replaced[this_char] = 1;
writer++;
}
// It's unique.
else if( counts[this_char] == 1 ) {
// Write it. Advance the writer position.
*writer = *reader;
writer++;
}
}
Это дает нам ***efCfB, почти там!
Последний шаг - обрезать строку там, где writer заканчивается после окончания чтения, в этом случае она указывает на C.Вы прекращаете чтение строк с нулевым байтом, поэтому после завершения цикла мы записываем нулевой байт.
*writer = '\0';
И мы здесь.