Lesson8. Leader - Dominator

Dominator - Find an index of an array such that its value occurs at more than half of indices in the array.

https://app.codility.com/programmers/lessons/8-leader/dominator/

문제요약

N개의 정수 배열 A가 주어지고 A에서 A의 길이의 절반보다 많이 등장하는 수를 dominator라고 한다. A의 dominator의 index 중 하나를 반환하거나 없으면 -1을 반환한다.

Assume that:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

For example, given array A such that

 A[0] = 3    A[1] = 4    A[2] =  3

 A[3] = 2    A[4] = 3    A[5] = -1

 A[6] = 3    A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

풀이

A의 각각에 대해 dictionary에 해당 수의 개수를 counting하면서 A의 절반보다 큰 경우에 해당 index를 반환한다. 전체를 다 처리하고 반환되지 않은 경우는 존재하지 않는 경우로 -1을 반환한다.

	def solution(A):
	dic = dict()
	half = len(A)/2
	for i in range(len(A)):
	if A[i] in dic:
	dic[A[i]] += 1
	else:
	dic[A[i]] = 1
	if dic[A[i]] > half:
	return i
	return -1

view raw 8_1_Dominator.py hosted with ❤ by GitHub