Так же сейчас не хватает интересных задачек по программированию, например как были по ассемблеру, когда учился у Олега Романовского.
Решил не пропускать интересные задачки и решать их в свободное время.
И так первая задача звучит так (услышал от Тумара Максима):
Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
число в этом массиве повторяется два раза. Найти это число за время O(N).
Решение ниже.
тут мы думаем ...
O(N) - это грубо говоря один проход по массиву, один for.
Сначала я пытался как-то хитро сортировать массив, смотреть на него как на дерево, но O(N) никак не получалось (за O(N) я принимал даже (O(a*N)+b) где a,b - константы), но потом понял, что использую не все данные.
Есть же ещё ограничение на элементы - максимальный M.
Идея решения:
создать массив длинной в M и инициализировать его например 0. Далее проходя по исходному массиву переписываем каждый элемент на своё место - массивДлинйМ[i]=i. Перед записью проверяя если на месте i в массиве уже 0, то значит элемент встретился 1 раз, если уже i то мы нашли дубликат.
Код на python:
import random
if __name__ == "__main__":
N = 10 #range of array
M = 100 #max possible value of element in array
#array of N-1 elements
arr_with_no_dup = random.sample(range(M), N-1)
#array with range of max element value
arr_of_all_elems = [x*0 for x in range(M)]
#position of element wich will be duplicated
elem_to_be_dup = random.sample(range(N-1), 1)[0]
#position of the duplicate
dup_pos = random.sample(range(N), 1)[0]
arr_with_dup = []
#make array with duplicated element
arr_with_dup = arr_with_no_dup[0:dup_pos] + [arr_with_no_dup[elem_to_be_dup]] + arr_with_no_dup[dup_pos:]
print arr_with_no_dup
print arr_with_dup
for i in arr_with_dup:
if arr_of_all_elems[i] != i:
arr_of_all_elems[i] = i
else:
print "duplicated element is ", i
break
результат выполнения:
[95, 91, 14, 23, 59, 10, 46, 34, 18]
[95, 46, 91, 14, 23, 59, 10, 46, 34, 18]
duplicate is 46
вот и всё. может есть ещё решения - предлагайте.
На решение ушла 1 пара :)
No comments:
Post a Comment