Каков наиболее эффективный способ обнаружения повторяющихся символов в строке в Java?

Question

Используя структуры данных (HashMap), я смог это сделать.

Это код:

import java.util.*;

class unique{
    public static void main(String[] args){
        HashMap<Character, Integer> charMap = new HashMap<Character, Integer>();
        boolean isNotUnique = false;
            for ( char loop : args[0].toCharArray() ){
            Integer freq = charMap.get( loop );
            charMap.put( loop, ( freq == null )? 1 : freq+1 );
            if ( charMap.get( loop ) > 1 )
            {
                isNotUnique = true;
            }
        }
            System.out.println ( isNotUnique );
    }
}

Без структур данных я придумал тупой подход. Это имеет O (n ^ 2)

class unique
{
    public static void main(String[] args)
    {
        String inputString = args[0];
        System.out.println( isUnique( inputString ) );

    }

    private static boolean isUnique(String inputString) {
        String methodString = inputString;
        for ( int i = 0; i < inputString.length(); i++ )
        {
            for ( int j = i+1; j < inputString.length(); j++ )
            {
                if ( methodString.charAt( i ) == methodString.charAt( j ) )
                {
                    return false;
                }
            }
        }
        return true;
    }
}

Мне было интересно, можно ли решить за O (n) время сложность

Answer 1

Если вам нужно поддерживать символы Юникода, которые не представлены суррогатными символами, это будет сделано:

private static boolean isUnique(String inputString) {
    long[] used = new long[1024];
    for (char c : inputString.toCharArray()) {
        if ((used[c >>> 6] & (1 << c)) > 0) {
            return false;
        }
        used[c >>> 6] |= 1 << c;
    }
    return true;
}

Он использует биты для экономии памяти. По сути, это то же самое, что если бы вы использовали массив логических значений:

private static boolean isUnique2(String inputString) {
    boolean[] used = new boolean[65536];
    for (char c : inputString.toCharArray()) {
        if (used[c]) {
            return false;
        }
        used[c] = true;
    }
    return true;
}

Если вам нужно только поддерживать символы ASCII, вы можете ограничить размер used в любом случае, чтобы уменьшить требуемую память (например, long[4] и boolean[256]). Ниже определенной длины inputString, вероятно, быстрее выполнить проверку n ^ 2, чем выделить для этого память. Так что в идеале вы делаете комбинацию из двух на основе длины.

Если вам нужно поддерживать все возможные символы Юникода, вам придется изменить это для поддержки суррогатных пар символов. Вы можете обнаружить их с помощью Character.isHighSurrogate(c). См. эту страницу для получения справки и поиска Google для получения более подробной информации.

Answer 2

Мне было интересно, можно ли решить за O (n) сложность времени:

Есть два простых решения, которые O(N) по времени:

• Подход HashSet - это O(N) во времени и O(N) в пространстве, где N - длина строки. (Обычный Java HashSet, содержащий N различных символов, будет занимать O(N) пробел с относительно большой константой пропорциональности.)

• Подход с использованием битового массива составляет O(N) во времени и O(1) в пространстве, но O(1) составляет 8 КБ (или 64 КБ, если вы используете boolean[]), и с этим связаны затраты на обнуление столько памяти, добавленной ко времени.

Ни один из них не является лучшим ответом во всех случаях.

• Для достаточно малых N простой вложенный цикл O(N^2) будет самым быстрым. (И он не использует дополнительную память.)

• Для средних N пользовательская хеш-таблица, в которой используется перефразировка при столкновении, будет лучше, чем HashSet или подход с использованием битового массива. Подход HashSet будет лучше, чем подход с битовыми массивами.

• Для достаточно больших N подход с использованием битового массива будет самым быстрым и использует наименьшее количество памяти.

(Для вышеизложенного я предполагаю, что входные строки не содержат повторяющихся символов. Если они есть, то фактическое значение N будет меньше длины строки.)

---

Если обнаружение повторяющихся символов должно справляться с суррогатными парами UTF-16, тогда простой подход состоит в том, чтобы транскодировать на лету кодовые точки Unicode и изменить структуры данных, чтобы использовать HashSet<Integer>, более крупные битовые массивы и т. Д.

И наоборот, если вы можете ограничить размер входного набора символов, вы можете уменьшить размер битовых массивов и т. Д.

Эти настройки будут иметь большое значение для того, где малые / средние / большие пороги могут упасть.

Answer 3

Какое определение у персонажа?az AZ или весь юникод?

если длина строки достаточно велика, например, миллион, вы можете создать массив int, длина массива - это длина вашего набора символов, и массив будет инициализированс нулем.

после этого, просмотрите строку в соответствии с каждым характером: array [(int) char] ++, чтобы вы могли легко найти время появления символа в массиве.

однако короткая строка не нуждается в таком методе.

этот метод O (n)