(codility with python) OddOccurrenceslnArray
lesson2 - OddOccurrenceslnArray
https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/
시간초과가 났던 로직이다. 아직 시간복잡도 계산이 어렵다.. for문 안에서 if문을 통해 배열을 탐색 O(n^2)의 시간복잡도가 걸린다.
# 테스트 케이스 시간초과 66%
def solution(A):
cand = []
dic = {}
for i in A:
if i in dic:
dic[i] += 1
else:
dic[i] = 1
for k, v in dic.items():
if v < 2:
cand.append(k)
return cand[0] if cand else 0
solution([])
Counter를 사용해 딕셔너리에 key-value형태로 만든다. for문 안에서 if문을 사용하기는 하지만 배열을 탐색하지 않고 값을 바로 비교한다. O(N)의 시간복잡도를 갖는다
from collections import Counter
def solution(A):
cand = Counter(A)
for i, v in cand.items():
if v % 2 != 0:
return i
solution([9, 3, 9, 3, 9, 7, 9])