Вопрос:
Учитывая строку, найдите в ней первый неповторяющийся символ и верните его индекс. Если этого не существует, верните -1.
first_unique(‘leetcode’) # 0 first_unique(‘loveleetcode’) # 2
Я придумал следующее решение. Как я могу сделать его более эффективным для очень длинных строк ввода?
def first_unique(self, s): if s == »: return -1 for item in s: if s.count(item) == 1: return s.index(item) break return -1 Лучший ответ:
Ваша версия неплоха для нескольких случаев с “хорошими” строками… но использование count довольно дорого для длинных “плохих” строк, я бы предложил вам элементы кэша, например:
def f1(s): if s == »: return -1 for item in s: if s.count(item) == 1: return s.index(item) break return -1 def f2(s): cache = set() if s == »: return -1 for item in s: if item not in cache: if s.count(item) == 1: return s.index(item) else: cache.add(item) return -1 import timeit import random import string random.seed(1) K, N = 500, 100000 data = ».join(random.choice(string.ascii_uppercase + string.digits) for _ in range(K)) print( timeit.timeit(‘f1(data)’, setup=’from __main__ import f1, data’, number=N)) print( timeit.timeit(‘f2(data)’, setup=’from __main__ import f2, data’, number=N))
Результаты на моем ноутбуке:
32.05926330029437 4.267771588590406
Версия, использующая кеш, дает вам коэффициент ускорения 8x против вашего, который все время использует функцию count. Итак, мой общий совет был бы… максимально возможным, насколько возможно
РЕДАКТИРОВАТЬ:
Я добавил версию Patrick Haugh к эталону и дал 10.92784585620725
EDIT2:
Я добавил версию Mehmet Furkan Demirel к эталону и дал 10.325440507549331
EDIT3:
Я добавил версию wim к эталону и дал 12.47985351744839
ВЫВОД:
Я бы использовал версию, которую я предложил первоначально, используя простой кеш, не полагаясь на модули счетчика Python, это не обязательно (с точки зрения производительности)
Ответ №1
Мое решение использует Counter для модуля collections.
from collections import Counter def first_unique(s): c = Counter(s) for i in range(len(s)): if c[s[i]] == 1: return i return -1 Ответ №2
Версия Suave:
from collections import Counter, OrderedDict class OrderedCounter(Counter, OrderedDict): pass def first_unique(s): counter = OrderedCounter(s) try: return counter.values().index(1) except ValueError: return -1
Странная версия:
from collections import OrderedDict def first_unique(s): nah = {0}-{0} # funny pair of eyes yeah = OrderedDict() for i,c in enumerate(s): if c not in nah: try: del yeah[c] except KeyError: yeah[c] = i else: nah.add(c) return next(yeah.itervalues(), -1) Ответ №3
Я бы использовал цикл for для итерации String с начала и каждого индекса, я бы проверял, имеет ли остальная часть String символ в текущем индексе с помощью Substring.
Попробуй это:
def firstUniqChar(word): for i in range(0,len(word)): ## iterate through the string if not word[i] in word[i+1:len(word)]: ## check if the rest contains that char index=i break return index
Надеюсь, поможет!
Ответ №4
Идея в этом решении заключается в использовании пары defaultdicts. Первый содержит целочисленное число каждого символа, а второе содержит местоположение индекса последнего прочитанного символа.
После прочтения всех символов, понимание списка используется, чтобы найти все те, которые только что произошли один раз (result). Минимальные местоположения указателей этих символов (найденные в нашем другом order умолчанию) дадут нам первое расположение указателей не повторяющихся символов.
from collections import defaultdict # To Create random string: from string import ascii_lowercase from random import choice, randint, seed # Create a random sentence of 1000 words (1-8 characters each). seed(0) gibberish = ‘ ‘.join(».join(choice(ascii_lowercase) for _ in range(randint(1, 8))) for _ in range(1000)) print(len(gibberish)) # Output: 5614 # Solution. def first_unique(s): dd = defaultdict(int) order = defaultdict(int) for n, c in enumerate(s): dd[c] += 1 order[c] = n result = [order[c] for c in dd if dd[c] == 1] return min(result) if result else -1
Задержки
%timeit first_unique(gibberish) 100 loops, best of 3: 2.13 ms per loop @wim solution: %timeit first_unique(gibberish) 100 loops, best of 3: 5.06 ms per loop @PatrickHaugh solution (which is much easier to understand than mine): %timeit first_unique(gibberish) 100 loops, best of 3: 4.2 ms per loop @BPL solution: %timeit f1(gibberish) 10 loops, best of 3: 39.2 ms per loop %timeit f2(gibberish) 1000 loops, best of 3: 890 µs per loop
Используя гораздо более короткое предложение из двадцати слов (133 символа):
%timeit first_unique(gibberish) 10000 loops, best of 3: 62.8 µs per loop @wim solution: %timeit first_unique(gibberish) 10000 loops, best of 3: 169 µs per loop @PatrickHaugh solution: %timeit first_unique(gibberish) 10000 loops, best of 3: 101 µs per loop @BPL solution: %timeit f1(gibberish) 10000 loops, best of 3: 55.1 µs per loop %timeit f2(gibberish) 10000 loops, best of 3: 31 µs per loop
Тестовые случаи.
s1 = ‘leetcode’ s2 = ‘loveleetcode’ >>> first_unique(s1) 0 >>> first_unique(s2) 2 Ответ №5 public class Main{ public static void main(String[] args) { System.out.println(«Input String : GirishRathi»); System.out.println(«Output String : » +firstUniqChar(«GirishRathi»)); } public static int firstUniqChar(String s) { Map<Character , Integer> map = new HashMap<Character , Integer>(); for(int i = 0 ; i < s.length() ; i++) { char current = s.charAt(i); if(map.containsKey(current)) { map.put(current, -1); }else { map.put(current , i); } } int min = Integer.MAX_VALUE; for(char c : map.keySet()) { if(map.get(c) > -1 && map.get(c) < min) { min = map.get(c); } } return min == Integer.MAX_VALUE ? -1 : min; } }
