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

Question

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

Navigation

#1 by (2 votes)

1

I made an algorithm that returns the minimum value between two distances in a given array. I would like to know 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 an array A non-empty with index zero consists of integers N, returns the minimum distance between the indices of this matrix that have adjacent values. The function should return -1 if the minimum distance is greater than 100 million. The function should return -2 if there are no adjacent indexes.

Assume this:

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

 Each element of array 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 the input storage (not

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#

asked by anonymous 10.02.2016 / 23:32

1 answer

How to use the service based database item in Visual Studio 2015? Calculate input with formatting (mascara)

score 2 · Answer 1

According to the answer:

Adjacent Values

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

One possibility, if the rule for valor adjacente is:

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

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

is in the SO post in English Compute Adjacent Pair (code extracted from the original answer):

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 described above , the code posted in the English OS is an alternative to solve the problem with O (n log n) complexity .