Сегодня у меня было собеседование по программированию, и это была одна из проблем. Не было никаких крайних случаев, и все входные данные были действительными. Однако следует учитывать временную сложность. Это сразу исключает использование вложенного цикла для проверки уникальности каждого отдельного символа. Моим вторым побуждением было использовать двухочковые. Это позволит использовать однопроходное решение. Я потратил около 15 минут на этот подход, но мне было трудно представить, как перемещать левый указатель при проверке уникальности. Из-за нехватки времени интервью я решил использовать другой метод, требующий двух невложенных циклов.

Решение 1

Это простой подход.

  1. Прокрутите строку и создайте объект с соответствующими счетчиками каждой буквы.
  2. Снова выполните цикл по строке, проверьте, равен ли счетчик 1, и верните этот индекс. В противном случае верните -1, если нет уникальных символов.

Решение 2

Это подход с двумя указателями, который я пытался реализовать.

  1. Оба указателя начинаются с 0.
  2. Ключом к этому подходу является проверка текущего количества левого указателя в объекте частоты символов. Если его счетчик равен › 1, мы знаем, что он не уникален, и левый указатель увеличивается. Не забудьте использовать здесь оператор continue.
  3. В противном случае добавьте символ к объекту частоты символов или увеличьте его.

Решение с двумя указателями по-прежнему довольно простое, но сегодня оно сбило меня с толку.

Оба подхода имеют временную сложность O(n). Первый подход состоит из двух проходов, а второй можно выполнить за один проход.