【Python】Codility in Python : Lesson 8 - Leader【Dominator】

Leader 第一題：【Dominator】
Find an index of an array such that its value occurs at more than half of indices in the array.

---

A zero-indexed array A consisting of N integers is given.
The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider 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 dominator of A is 3 because it occurs in 5 out of 8 elements of A
(namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

　　def solution(A)

that, given a zero-indexed array A consisting of N integers,
returns index of any element of array A in which the dominator of A occurs.
The function should return −1 if array A does not have a dominator.

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.

---

方法一：使用 groupby 的方式再 loop 慢慢解
Correctness：100%、Performance：100%

from itertools import groupby

def solution(S):
  if len(A) == 1:
    return 0

  dominator = -1
  dominatorCount = 0
  for k, v in groupby(sorted(A)):
    length = len(list(v))
    if(length > dominatorCount):
      dominator = k
      dominatorCount = length

  if dominator == -1:
    return -1

  index = -1
  for i in range(0, len(A) - 1):
    if(A[i] == dominator):
      if(i == 0 or A[i] == A[i+1]):
        index = i

  return index if(dominatorCount > (len(A) / 2)) else -1

完整練習題 source code 請參閱：github