Algorithm help
A vector with n images A = [1 ... n] has a majority image I if more than half of the vector images are equal I. You can use A [i] = A [j ] to check if the images in the i and j positions are the same. Show how to solve this problem in O (nlogn) time using a divide and conquer approach
What I thought: Can someone here help me put together an algorithm for this problem. A vector with n images A = [1 ... n] has a majority image I if more than half of the vector images are the same I. You can use A [i] = A [j] to check if the images in positions i and j are equal. Show how to solve this problem in O (nlogn) time using a division and conquest approach
EDIT MY SOLUTION:
Divide the two-part vector n / 2 - > A and A2 find n1 which is the major element (image) of A find n2 which is the major element (image) of A2 check if the count of n1 or n2 is greater than the mean size plus 1 of vector A.
Algoritmo:
majoritario(V[1......m])
se (m==1)
retorna V[1]
meio= ceil(m/2) pegar o teto
L_elemento= majoritaio(V[1....meio]
R_elemento= majoritario(V[meio+1....m]
se L_elemento == R_elemento : retornar L_elemento
L_soma = freq(V[1...m],L_elemento)
R_soma= freq(V[1...m], R_elemento)
se R_soma > meio+1: retorna R_elemento
se nao se L_soma> meio+1 retorna L_elemento
se não
retorna não tem elemento majoritario.
Freq(V[1...m], elemento)
para i=1 até m
se V[1] == elemento
conta = conta +1
retorna conta.
My final idea was to pass the halves recursively. The majority algorithm has two recursive calls.
2*T(n/2)
and the element count is resolved at a time O (n) worst case. then we have a recurrence
T(n) = 2T(n/2) +O(n) e pelo teorema mestre
T(n) = aT(n/b) +O(n^c)
c = logb na base a
c = 1,a=2,b =2 ou seja
O(nlogn)
I think that would be the resolution, I'm not sure .. Thank you.
My idea was to follow this line, but I do not know if I'm correct.