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

Question

me he quedado atrapado en la solución de la siguiente pregunta práctica de la entrevista:
tengo que escribir una función:

int triangle(int[] A); 

que, dada una matriz cero indexada A que consiste en 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 triples 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 array A tales 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 la triple (0, 2, 4) cumple todas las condiciones requeridas.

Para array A tales que

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

la función debe devolver 0.

Si hago un ciclo triple, esto sería muy, muy lento (complejidad: O(n^3)). Estoy pensando en utilizar para almacenar una copia extra de la matriz y ordenarla, y utilizar una búsqueda binaria para un número en particular. Pero no sé cómo resolver este problema.
¿Alguna idea?

Answer 1

Antes que nada, puede ordenar su 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., por lo que las otras 2 desigualdades son automáticamente verdaderas.

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

A continuación, es suficiente para comprobar que A[i] + A[j] > A[j+1], porque otra A[k] son incluso más grandes (por lo que si la desigualdad se cumple para algunos k, que vale para k = j + 1 también).

A continuación, es suficiente para comprobar que A[j-1] + A[j] > A[j+1], porque otra A[i] son aún más pequeños (por lo que si la desigualdad se cumple para algún i, que tiene para i = j - 1 también).

Por lo tanto, solo tiene una verificación lineal: debe verificar si al menos un jA[j-1] + A[j] > A[j+1] es verdadero.

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

---

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

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

Answer 2

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

Answer 3

En Ruby ¿qué pasa con

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 

Sólo portarlo en el idioma de su elección

Answer 4

Aquí es una implementación del algoritmo propuesto por Vlad. La pregunta ahora requiere evitar desbordamientos, por lo tanto, los moldes a 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 5

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 6

Una solución 100/100 php: 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 7

Python:

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 

Ordenando: complejidad O Loglineal (N log N)

Answer 8

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

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 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

Revertir el bucle de la solución 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 por A [k-2] + A [k-1]> A [k]. Explicado en palabras, la suma de los dos últimos números más grandes debería 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 ciclo.

Además, podemos agregar el cheque para 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 11

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

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 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 tiempo de complejidad. El concepto es simple usar el formaula que dieron extrayendo una serie de tríos de elementos ordenados.