Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar um programa para encontrar o elemento que aparece na maioria das células de um vetor usando divisão e conquista?

+2 votos
93 visitas
perguntada Mai 6, 2016 em Ciência da Computação por Saulo (426 pontos)  

Escreva um programa para encontrar o elemento que aparece na maioria das células de um vetor (ou informar que ele não existe se esse for o caso, retornando -1) usando a estratégia de divisão e conquista. Se o vetor tem tamanho \(n\), então esse elemento deve aparecer pelo menos \( \lfloor n/2 \rfloor +1 \). Por exemplo, no vetor \([4, 2, 3, 4, 4, 4]\) o elemento que aparece a maioria das vezes é 4. No caso do vetor \([4, 1, 2, 3, 4, 4, 4]\), o elemento que aparece a maioria das vezes também é o 4. Suponha que você não pode ordenar os elementos, mas apenas compará-los. Qual a complexidade desse algoritmo?

Compartilhe

3 Respostas

+4 votos
respondida Mai 6, 2016 por Saulo (426 pontos)  

Código-fonte:

import copy

def encontra_elemento_maioria(X):
    n = len(X)
    if (n > 1):
        n_middle = int(n/2)
        A = copy.deepcopy(X[0:n_middle])
        B = copy.deepcopy(X[n_middle:n])
        elem_maioria_A = encontra_elemento_maioria(A)
        elem_maioria_B = encontra_elemento_maioria(B)
        return merge_elemento_maioria(A, B, elem_maioria_A, elem_maioria_B)
    else:
        return X[0]

def merge_elemento_maioria(A,B,elem_maioria_A,elem_maioria_B):
    if (elem_maioria_A != elem_maioria_B):
        freq_A, freq_B = 0, 0
        for i in range(0, len(A)):
            if (A[i]==elem_maioria_A):
                freq_A += 1
            elif (A[i]==elem_maioria_B):
                freq_B += 1

        for j in range(0, len(B)):
            if (B[i]==elem_maioria_A):
                freq_A += 1
            elif (B[i]==elem_maioria_B):
                freq_B += 1

        if (freq_A >= int((len(A)+len(B))/2)+1):
            return elem_maioria_A
        elif (freq_B >= int((len(A)+len(B))/2)+1):
            return elem_maioria_B
        else:
            return -1
    else:
        return elem_maioria_A

if __name__ == '__main__':
    X = [4, 2, 3, 4, 4, 4]
    print X
    print encontra_elemento_maioria(X)

    X = [4, 1, 2, 3, 4, 4, 4]
    print X
    print encontra_elemento_maioria(X)

Complexidade:
\( T(n) = 2T(n/2) + f(n) \), com \( f(n) \in O(n) \).
Pelo Master theorem, como \( f(n)=\Theta(n^{\log_{2}{2}}) \), então \( T(n) = \Theta(n^{\log_{2}{2}} \, lg \, n) = \Theta(n \, lg \, n) \)

+1 voto
respondida Mai 7, 2016 por PRosa (61 pontos)  

Uma outra solução é com o uso de pilha de pilhas:

def Maioria():
    vet=[4,1,2,3,4,4,4]   
    # Divida: divide o vetor original em pilhas de cada elemento    
    pilha=[]
    for i in range(len(vet)):
        achou=False               
        if len(pilha)>0:
           for j in range(len(pilha)):
               if pilha[j][0]==vet[i]:
                   achou=True
                   break
        if not achou:
           pilha.append([vet[i]])                   
        else:
           pilha[j].append(vet[i])

    #Conquiste: utilizando todas as partes (pilhas individuais), acha o elemento
    indMaioria,qtdeMaioria=0,0 
    for i in range(len(pilha)):
        if len(pilha[i])>qtdeMaioria:
            qtdeMaioria=len(pilha[i])
            indMaioria=i            

    if (qtdeMaioria >= (len(vet)//2 + 1)):
        print "Elemento %i encontrado %i vezes" % (pilha[indMaioria][0],qtdeMaioria)
    else:
        print "Não encontrado elemento de maioria."
comentou Mai 8, 2016 por Saulo (426 pontos)  
Fala Paulo! Boa! Mas essa é uma solução força-bruta, certo? Só vou fazer um comentário para acrescentar, fins didáticos apenas. Uma solução "clássica" (e muito poderosa) para fazer isso que você fez, é usando um dicionário e ir acumulando as frequências (no caso do seu código, é o tamanho da pilha de cada número). Você consegue fazer usando apenas um for. Veja:

    def Maioria():
        vet=[4,1,2,3,4,4,4]
        
        mapaElemFreq = dict()
        numFreqMax, freqMax = -1, 0
        
        for i in range(len(vet)):
            num = vet[i]
            
            if (not mapaElemFreq.has_key(num)):
                mapaElemFreq[num] = 0
                
            mapaElemFreq[num] += 1
            
            if (mapaElemFreq[num] > freqMax):
                freqMax = mapaElemFreq[num]
                numFreqMax = num
    
        if (freqMax >= (len(vet)//2 + 1)):
            print "Elemento %i encontrado %i vezes" % (numFreqMax, freqMax)
        else:
            print "Nao encontrado elemento de maioria."
comentou Mai 8, 2016 por PRosa (61 pontos)  
Oi Saulo, que interessante o uso de dicionários para a solução! Acho que ambas utilizam o raciocínio de divisão e conquista, pois partem de uma pilha/lista maior para gerar pilhas menores e então encontrar a maior pilha entre as partes, embora não utilizem recursão. O código ficou bem enxuto!
+1 voto
respondida Mai 10, 2017 por Caue (226 pontos)  

Outra Solução:

def maioria(s):
    l = len(s)
    if l == 1:
        return s[0]
    else:
        m1 = maioria(s[:l // 2])
        m2 = maioria(s[l // 2:])

        if m1 == m2:
            return m1
        else:
            c1, c2 = 0, 0
            for x in s:
                if x == m1:
                    c1 += 1
                elif x == m2:
                    c2 += 1
            if c1 >= l // 2 + 1:
                return m1
            elif c2 >= l // 2 + 1:
                return m2
            else:
                return -1


seq = [4, 1, 2, 3, 4, 4, 8, 4, 5, 7, 4, 4, 4]
print(seq)
print(maioria(seq))
...