1

Estou aprendendo a programar e estou fazendo os exercícios de algoritmos do hackerrank. Estou no exercicio migratory birds.

Para ter acesso ao exercício é necessário acesso com login. Como muitos não tem acesso, vou copiar e colar o exercício aqui:

You have been asked to help study the population of birds migrating across the continent. Each type of bird you are interested in will be identified by an integer value. Each time a particular kind of bird is spotted, its id number will be added to your array of sightings. You would like to be able to find out which type of bird is most common given a list of sightings.If two or more types of birds are equally common, choose the type with the smallest ID number.

Function Description

Complete the migratoryBirds function in the editor below. It has two parameters:

Integer, , denoting the number of elements in the input array. Integer Array, , with array elements denoting the respective type numbers of each bird in the flock. The function must return an integer denoting the type number of the most common bird.

Raw Input Format

The first line contains an integer denoting n, the number of birds sighted and reported in the array . The second line describes ar as n space-separated integers representing the type numbers of each bird sighted.

Pessoal,

a minha solução é essa daqui:

function migratoryBirds($n, $ar) { 
    $ret = [];

    for ( $i = 0 ; $i < $n ; $i++ ){        
        $frequencia = 0;
        for ( $k = 0 ; $k < $n ; $k++) { 
            if( $ar[ $i ] == $ar[ $k ] ) {
                $ret[ $ar[ $i ] ] = 1 + $frequencia;
                $frequencia++;
            }   
        }
    }
    $arrayMaiorFrequencia = $ret[ $ar[0] ];
    $menorChaveArrayMaiorFrequencia = $ar[0];

    for ( $i = 0; $i < $n; $i++ ) {
        if( $ret[ $ar[$i] ] == $arrayMaiorFrequencia && $ar[$i] < $menorChaveArrayMaiorFrequencia ) {
            $menorChaveArrayMaiorFrequencia = $ar[$i];
        } elseif($ret[ $ar[$i] ] > $arrayMaiorFrequencia) {
            $arrayMaiorFrequencia = $ret[ $ar[$i] ];    
            $menorChaveArrayMaiorFrequencia = $ar[$i];
        }
    }

    return $menorChaveArrayMaiorFrequencia;
}

Os inputs da função são definidos pelo exercício, ou seja, $ar é um array de int e $n é o número de elementos do array.

Porém, eu quero saber se é possível fatorar esta solução? Observação: apesar de estar usando php, e algumas funções em php tornariam a solução muito mais fácil e rápida, NÃO POSSO UTILIZAR NENHUMA FUNÇÃO DO PHP, somente o conceito de algoritmos. Sendo assim, como torno a minha solução mais limpa?

3
  • Mas a solução tem de ser em php ou não ? Se for o caso é apropriado colocar essa tag na pergunta. Aproveito também para perguntar que não ficou muito claro para mim, qual o conteúdo de $ar ? Tem como colocar um var_dump de exemplo ?
    – Isac
    Commented 18/04/2018 às 10:20
  • @Isac, não é necessário ser em php, mas não posso usar funções. Estou utilizando php porque comecei a aprender por ela. Um var_dump($ar) seria, por exemplo, [3,4,2,5,4] e a função migratoryBirds deveria retornar 4, porque é o elemento que mais aparece (maior frequência) no array. Outro exemplo, var_dump($ar) = [5,5,5,3,3,3]. A return da função seria 3. Tendo 5 e 3 as maiores frequencias, porém frequências iguais, a função migratoryBirds deverá retornar o tipo de menor valor.
    – gmilleo
    Commented 18/04/2018 às 10:39
  • @Isac, ficou confuso o início do meu comentário.. Posso usar qualquer linguagem, mas não as funções dela, somente algoritmos
    – gmilleo
    Commented 18/04/2018 às 10:46

2 Respostas 2

0

Começo por dizer que não necessita de ter 2 for para calcular as frequências:

$ret = [];

for ( $i = 0 ; $i < $n ; $i++ ){        
    $frequencia = 0;
    for ( $k = 0 ; $k < $n ; $k++) { 

Pode muito bem faze-lo apenas com um for incrementando na posição que interessa, funcionando assim como um mapa. Quanto ao achar o menor, tanto o seu if como else if deveriam ter caminhos iguais facilitando o algoritmo. Como pequeno aparte para arrays normais, se não precisa de utilizar os indices especificamente, torna-se mais simples utilizar foreach, pois evita de ter que indexar constantemente.

Tendo em conta esses pontos que referi, e assumindo a nomenclatura das variaveis em português, para coincidir com o que tem, poderia fazer assim:

function migratoryBirds($n, $ar) { 
    $passaros = [];
    foreach ($ar as $passaro){
        $passaros[$passaro] = ($passaros[$passaro] ?? 0) + 1;
    }

    $maiorContagem = 0;
    $menorId = $ar[0];
    foreach ($passaros as $id => $contagem) {
        if ($contagem > $maiorContagem || ($contagem == $maiorContagem && $id < $menorId)){
            $maiorContagem = $contagem;
            $menorId = $id;
        }
    }

    return $menorId;
}

Veja o código a funcionar no Ideone

Repare que nesta minha solução juntei ambos os casos de verificação de contagem maior ou contagem igual e id menor:

if ($contagem > $maiorContagem || ($contagem == $maiorContagem && $id < $menorId)){

Tornando esta parte mais simples.

Fiz a contagem inicial de frequências apenas com um for e servi-me do null coalescing operator para ir buscar o valor que a contagem para aquele pássaro já tinha ou zero caso não existisse:

($passaros[$passaro] ?? 0)

Naturalmente poderia fazer isto de outras formas, por exemplo à custa de isset, se quisesse suportar versões mais antigas do php.

Edit:

Certamente dá para solucionar apenas com for e não foreach, apenas optei pelo foreach pois é mais simples e idiomático. Alterando a minha solução para fazer uso de apenas for para achar as frequências ficaria assim:

$passaros = [];
for ($i = 0; $i < $n; $i++){
    $passaros[$ar[$i]] = ($passaros[$ar[$i]] ?? 0) + 1;
}

De acordo com a minha solução não é possivel de utilizar um for simples na verificação do maior, que é o laço/ciclo seguinte, pois apenas algumas posições estão definidas.

No seu exemplo de entrada de [5,5,5,3,3,3] o array de contagens fica assim:

array(2) {
  [5]=>
  int(3)
  [3]=>
  int(3)
}

Aqui vê que apenas a posição 3 e 5 estão atribuídas, o que significa que não posso passar pelas posições 0,1,2,etc... até ao tamanho que seria 2.


Também pode fazer este primeiro for sem null coalescing operator e servindo-se de isset:

$passaros = [];
for ($i = 0; $i < $n; $i++){
    //se a contagem para este pássaro ainda não existe define como 0
    if(!isset($passaros[$a[$i]]){
        $passaros[$ar[$i]] = 0;
    }

    $passaros[$ar[$i]]++;
}
4
  • como poderia achar as frequencias utilizando somente um for e nao usando o foreach?
    – gmilleo
    Commented 18/04/2018 às 13:17
  • @Guilherme Editei a resposta com mais informação relativa a isso.
    – Isac
    Commented 18/04/2018 às 13:39
  • qual seria o comportamento dos 2 pontos de interrogação? "??" Conheço operadores ternários ( ? e : ). Qual a diferença?
    – gmilleo
    Commented 18/04/2018 às 15:43
  • @Guilherme O ?? é o null coalescing operator que mencionei na resposta. O que ele faz é devolver o valor da expressão (o que está antes de ?? ) caso exista, e caso não exista devolve o que tá a direita. Na documentação oficial consegue ver exemplos disso. Como exemplo simples $a ?? 10 resulta em $a se $a existir e for diferente de nulo ou 10 caso contrário. Como nota esta funcionalidade está disponível a partir da versão 7 do php.
    – Isac
    Commented 18/04/2018 às 16:00
0

@Isac,

Consegui chegar na seguinte solução, utilizando 1 for e 1 if somente

function migratoryBirds($n, $ar) { 
    $contagem = 0;
    $passaro = [];
    $maior = 0;
    $menorChave= 0 ;
    for($i=0; $i < $n; $i++ ){
        $passaro[$ar[$i]] = ( $passaro[ $ar[$i] ] ?? 0 ) + 1;
        if($passaro[$ar[$i]] > $maior || $passaro[$ar[$i]] == $maior && $ar[$i] < $menorChave ) {
            $maior = $passaro[$ar[$i]];
            $menorChave = $ar[$i];  
        }
    }   
    return $menorChave;
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .