1

Fiz um algoritmo que retorna o valor minimo entre duas distancias em um determinado array. Gostaria de saber se ainda ha alguma forma de melhorar o algoritmo olhando para complexidade O(N*log(N)). Abaixo o enunciado.

Escrever uma função que, dado um array A não-vazia com índice zero consiste em inteiros N, retorna o mínimo distância entre os índices desta matriz que têm valores adjacentes. A função deve retornar -1 se a distância mínima é superior a 100 milhões. A função deve retornar -2 se não houver índices adjacentes.

Assuma isso:

 N é um número inteiro dentro do intervalo [1..40,000];

 cada elemento da matriz A é um número inteiro dentro do intervalo

[-2,147,483,648..2,147,483,647]

Complexidade:

 esperado complexidade de tempo de pior caso é O (N * log (N));

 esperado espaço de complexidade do pior caso é O (N), além do armazenamento de entrada (não

public static int solution(int[] A)
                {
                    int resultado = int.MaxValue;

                    if (A.Length < 2 || A == null)
                        return -2;

                    for (int i = 0; i < A.Length - 1; i++)
                    {
                        for (int j = i + 1; j < A.Length; j++)
                        {
                            if (Math.Abs(A[i] - A[j]) < resultado)
                                resultado = Math.Abs(A[i] - A[j]);
                        }
                    }

                    if (resultado > 100000000)
                        return -1;

                    return resultado;
                }
1
  • A pergunta é se o código esta ok, sim esta ok... funciona para oque você informou no enunciado. Existem sim algumas variações.. você pode utilizar algumas opções do c# para facilitar algumas coisas como Tupple, Listas etc... e até mesmo multitarefas(multithread). 11/02/2016 às 18:41

1 Resposta 1

2

Conforme a resposta:

Valores adjacentes

Aparentemente, falta a definição do que é valor adjacente para o problema descrito na pergunta.

Uma possibilidade, caso a regra para valor adjacente seja:

...
Um array A não-vazio com índice zero contém N inteiros.

Um par de índices (P, Q) onde 0 ≤ P < Q < N, é dito adjacente, se nenhum valor "encontra-se estritamente" entre A[P] e A[Q].
...


está no post do SO em inglês Compute Adjacent Pair (código extraído da resposta original):

Array.Sort(A);

for (int i = 0; i < A.Length - 1; i++)
{
    // equivalent to
    // if (Math.Abs(A[i] - A[i + 1]) < shortestDistance)
    //  shortestDistance = Math.Abs(A[i] - A[i + 1]);
    shortestDistance = Math.Abs(A[i] - A[i + 1]) < shortestDistance ? Math.Abs(A[i] - A[i + 1]) : shortestDistance;
}

// return −1 if the minimum distance is greater than 100,000,000
if (shortestDistance > 100000000)
{
    return -1;
}

return shortestDistance;


Complexidade:

  • Ordenar o vetor: O(N*log(N))

  • Encontrar o menor valor: O(N)

Como: O(N*log(N) + N) = O(N*log(N))

Portanto, caso a regra seja a descrita acima, o código postado no SO em inglês é uma alternativa para solucionar o problema com uma complexidade O(n log n).

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 .