Algorithm of adjacent numbers with complexity O (N * log (N))

Asked

Viewed 754 times

1

I made an algorithm that returns the minimum value between two distances in a given array. I wonder if there is still some way to improve the algorithm by looking at complexity O(N*log(N)). Below the statement.

Write a function that, given a non-empty A array with zero index consists of integers N, returns the minimum distance between the indexes of this matrix that have adjacent values. The function must return -1 if the minimum distance is greater than 100 million. The function must return -2 if there are no adjacent indexes.

Assume that:

N is an integer within the range [1.. 40,000];

each element of matrix A is an integer within the range

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

Complexity:

expected worst case time complexity is O (N * log (N));

expected worst case complexity space is O(N), in addition to input storage (no

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;
                }
c#

  • The question is whether the code is ok, yes this ok... works for what you reported in the statement. There are some variations.. you can use some c# options to facilitate some things like Tupple, Lists etc... and even multitasking (multithread).

1 answer

2

According to the answer:

Adjacent values

Apparently, the definition of what is valor adjacente for the problem described in the question.

A possibility, if the rule for valor adjacente be it:

...
A non-empty zero-index A array contains integers N.

An index pair (P, Q) where 0 P < Q < N is said to be adjacent, if no value "is strictly" between A[P] and A[Q].
...


is in the post of ONLY in English Compute Adjacent Pair (code extracted from the original response):

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;


Complexity:

  • Sort the vector: O(N*log(N))

  • Find the lowest value: O(N)

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

Therefore, if the rule is as described above, the code posted in the OS in English is an alternative to solving the problem with a complexity O(n log n).

Browser other questions tagged c#

You are not signed in. Login or sign up in order to post.