c++ - triangulos - ¿Cómo saber que existe un triángulo triple en nuestra matriz?

triangulos significado espiritual

Question

Estaba atascado en resolver la siguiente pregunta de práctica de entrevista:
Tengo que escribir una función:

int triangle(int[] A);

dado que una matriz indexada a cero A que consta de N enteros devuelve 1 si existe un triple (P, Q, R) tal que 0 < P < Q < R < N .

A[P] + A[Q] > A[R],  
A[Q] + A[R] > A[P],  
A[R] + A[P] > A[Q].

La función debe devolver 0 si tal triple no existe. Supongamos que 0 < N < 100,000 . Supongamos que cada elemento de la matriz es un número entero en el rango [-1,000,000..1,000,000] .

Por ejemplo, dada la matriz A tal que

A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20

la función debe devolver 1 , porque el triple (0, 2, 4) cumple todas las condiciones requeridas.

Para la matriz A tal que

A[0]=10, A[1]=50, A[2]=5, A[3]=1

la función debe devolver 0 .

Si hago un triple ciclo, esto sería muy muy lento (complejidad: O(n^3) ). Pienso tal vez usarlo para almacenar una copia extra de la matriz y ordenarla, y usar una búsqueda binaria para un número en particular. Pero no sé cómo solucionar este problema.
¿Algunas ideas?

Answer 1

Aquí está mi solución en C #, que obtiene una corrección del 90% (la respuesta incorrecta se devuelve para la prueba extreme_arith_overflow1 -overflow test, 3 MAXINTs- ) y 100% de rendimiento.

private struct Pair
{
    public int Value;
    public int OriginalIndex;
}

private static bool IsTriplet(Pair a, Pair b, Pair c)
{
    if (a.OriginalIndex < b.OriginalIndex && b.OriginalIndex < c.OriginalIndex)
    {
        return ((long)(a.Value + b.Value) > c.Value
                && (long)(b.Value + c.Value) > a.Value
                && (long)(c.Value + a.Value) > b.Value);
    }
    else if (b.OriginalIndex < c.OriginalIndex && c.OriginalIndex < a.OriginalIndex)
    {
        return ((long)(b.Value + c.Value) > a.Value
                    &&(long)(c.Value + a.Value) > b.Value
                    && (long)(a.Value + b.Value) > c.Value);
    }
    // c.OriginalIndex < a.OriginalIndex && a.OriginalIndex < b.OriginalIndex
    return ((long)(c.Value + a.Value) > b.Value
                && (long)(a.Value + b.Value) > c.Value
                && (long)(b.Value + c.Value) > a.Value);
}

public static int Triplets(int[] A)
{
    const int IS_TRIPLET = 1;
    const int IS_NOT_TRIPLET = 0;

    Pair[] copy = new Pair[A.Length];

    // O (N)
    for (var i = 0; i < copy.Length; i++)
    {
        copy[i].Value = A[i];
        copy[i].OriginalIndex = i;
    }

    // O (N log N)
    Array.Sort(copy, (a, b) => a.Value > b.Value ? 1 : (a.Value == b.Value) ? 0 : -1);

    // O (N)
    for (var i = 0; i < copy.Length - 2; i++)
    {
        if (IsTriplet(copy[i], copy[i + 1], copy[i + 2]))
        {
            return IS_TRIPLET;
        }
    }

    return IS_NOT_TRIPLET;
}

Answer 2

Aquí hay una implementación del algoritmo propuesto por Vlad. La pregunta ahora requiere evitar desbordamientos, por lo tanto, los moldes son long long .

#include <algorithm>
#include <vector>

int solution(vector<int>& A) {

    if (A.size() < 3u) return 0;

    sort(A.begin(), A.end());

    for (size_t i = 2; i < A.size(); i++) {
        const long long sum = (long long) A[i - 2] + (long long) A[i - 1];
        if (sum > A[i]) return 1;
    }

    return 0;

}

Answer 3

En Java:

public int triangle2(int[] A) {

    if (null == A)
        return 0;
    if (A.length < 3)
        return 0;

    Arrays.sort(A);

    for (int i = 0; i < A.length - 2 && A[i] > 0; i++) {
        if (A[i] + A[i + 1] > A[i + 2])
            return 1;
    }

    return 0;

}

Answer 4

En primer lugar, puedes ordenar tu secuencia. Para la secuencia ordenada es suficiente verificar que A[i] + A[j] > A[k] para i < j < k , porque A[i] + A[k] > A[k] > A[j] etc., entonces las otras 2 desigualdades son automáticamente verdaderas.

(De ahora en adelante, i < j < k .)

A continuación, basta con comprobar que A[i] + A[j] > A[j+1] , porque otros A[k] son aún más grandes (entonces, si la desigualdad se mantiene para algunos k , se mantiene para k = j + 1 también).

A continuación, basta con comprobar que A[j-1] + A[j] > A[j+1] , porque otros A[i] son aún más pequeños (por lo tanto, si la desigualdad se mantiene para algunos i , se mantiene para i = j - 1 también).

Entonces, solo tiene una comprobación lineal: debe comprobar si para al menos un j A[j-1] + A[j] > A[j+1] mantiene verdadero.

En total O(N log N) {sorting} + O(N) {check} = O(N log N) .

Abordar el comentario sobre los números negativos: de hecho, esto es lo que no consideré en la solución original. Teniendo en cuenta que los números negativos no cambia mucho la solución, ya que ningún número negativo puede ser parte de un triángulo triple . De hecho, si A[i] , A[j] y A[k] forman un triángulo triple, entonces A[i] + A[j] > A[k] , A[i] + A[k] > A[j] , que implica 2 * A[i] + A[j] + A[k] > A[k] + A[j] , por lo tanto 2 * A[i] > 0 , entonces A[i] > 0 y por simetría A[j] > 0 , A[k] > 0 .

Esto significa que podemos eliminar de forma segura los números negativos y ceros de la secuencia, lo que se realiza en O(log n) después de la clasificación.

Answer 5

En ruby ​​que tal

def check_triangle (_array)
  for p in 0 .. _array.length-1
    for q in p .. _array.length-1
      for r in q .. _array.length-1
        return true if _array[p] + _array[q] > _array[r] && _array[p] + _array[r] > _array[q] && _array[r] + _array[q] > _array[p]
      end
    end
  end

  return false
end

Solo cuélguelo en el idioma de su elección.

Answer 6

Haga una ordenación rápida primero, esto generalmente tomará nlogn. Y puede omitir el tercer bucle por búsqueda binaria, que puede tomar log (n). Entonces, en conjunto, la complejidad se reduce a n ^ 2log (n).

Answer 7

Pitón:

def solution(A):
    A.sort()
    for i in range(0,len(A)-2):
        if A[i]+A[i+1]>A[i+2]:
            return 1
    return 0

Clasificación: Loglinear complejidad O (N log N)

Answer 8

Revertir el bucle de la solución de Vlad para mí parece ser más fácil de entender.

La ecuación A [j-1] + A [j]> A [j + 1] podría cambiarse a A [k-2] + A [k-1]> A [k]. Explicado en palabras, la suma de los dos últimos números más grandes debe ser mayor que el valor más grande actual que se está verificando (A [k]). Si el resultado de sumar los dos últimos números más grandes (A [k-2] y A [k-1]) no es mayor que A [k], podemos pasar a la siguiente iteración del bucle.

Además, podemos agregar la verificación de los números negativos que Vlad mencionó, y detener el ciclo antes.

int solution(vector<int> &A) {
    sort(A.begin(),A.end());
    for (int k = A.size()-1; k >= 2 && A[k-2] > 0 ; --k) {
        if ( A[k-2]+A[k-1] > A[k] )
            return 1;
    }
    return 0;
}

Answer 9

Solución PHP:

function solution($x){
    sort($x);
    if (count($x) < 3) return 0; 
    for($i = 2; $i < count($x); $i++){
        if($x[$i] < $x[$i-1] + $x[$i-2]){
            return 1;
        }
    }

    return 0;
}

Answer 10

Tengo otra solución para contar triángulos. Su complejidad de tiempo es O (N ** 3) y lleva mucho tiempo procesar arrays largos.

Private Function solution(A As Integer()) As Integer
    '' write your code in VB.NET 4.0
    Dim result, size, i, j, k As Integer
        size = A.Length
        Array.Sort(A)
        For i = 0 To Size - 3
            j = i + 1
            While j < size
                k = j + 1
                While k < size
                    If A(i) + A(j) > A(k) Then
                        result += 1
                    End If
                    k += 1
                End While
                j += 1
            End While
        Next
        Return result
End Function

Answer 11

Una solución de php 100/100: http://www.rationalplanet.com/php-related/maxproductofthree-demo-task-at-codility-com.html

function solution($A) {
    $cnt = count($A);
    sort($A, SORT_NUMERIC);
    return max($A[0]*$A[1]*$A[$cnt-1], $A[$cnt-1]*$A[$cnt-2]*$A[$cnt-3]);
}

Answer 12

public static int solution(int[] A) {
    // write your code in Java SE 8
    long p, q, r;
    int isTriangle = 0;

    Arrays.sort(A);
    for (int i = 0; i < A.length; i += 1) {

        if (i + 2 < A.length) {
            p = A[i];
            q = A[i + 1];
            r = A[i + 2];
            if (p >= 0) {
                if (Math.abs(p) + Math.abs(q) > Math.abs(r) && Math.abs(q) + Math.abs(r) > Math.abs(p) && Math.abs(r) + Math.abs(p) > Math.abs(q))
                    return 1;
            }
        } else return 0;


    }

    return isTriangle;

}

La implementación anterior es lineal en complejidad de tiempo. El concepto es simple usar la fórmula que dieron extrayendo una serie de trillizos de elementos ordenados.