Как узнать, что треугольник-тройка существует в нашем массиве?

Question

Я застрял в решении следующего вопроса о практике интервью:
Мне нужно написать функцию:

int triangle(int[] A);

, для которой задан индексированный нулем массив A, состоящий из N целых чисел, возвращает 1 если существует тройка (P, Q, R) такая, что 0 < P < Q < R < N.

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

Функция должна возвращать 0, если такой тройки не существует.Предположим, что 0 < N < 100,000.Предположим, что каждый элемент массива представляет собой целое число в диапазоне [-1,000,000..1,000,000].

Например, данный массив A такой, что

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

функция должна возвращать 1, посколькутройка (0, 2, 4) удовлетворяет всем необходимым условиям.

Для массива A, для которого

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

, функция должна вернуть 0.

Если ясделать тройной цикл, это будет очень очень медленно (сложность: O(n^3)).Я думаю, может быть, использовать для хранения дополнительной копии массива и сортировки его, а также использовать двоичный поиск для определенного числа.Но я не знаю, как решить эту проблему.
Есть идеи?

Answer 1

Прежде всего, вы можете отсортировать свою последовательность. Для отсортированной последовательности достаточно проверить, что A[i] + A[j] > A[k] для i < j < k, потому что A[i] + A[k] > A[k] > A[j] и т. Д., Поэтому два других неравенства автоматически выполняются.

(С этого момента i < j < k.)

Далее достаточно проверить, что A[i] + A[j] > A[j+1], потому что другие A[k] еще больше (поэтому, если неравенство выполняется для некоторых k, оно также справедливо и для k = j + 1).

Далее достаточно проверить, что A[j-1] + A[j] > A[j+1], потому что другие A[i] еще меньше (поэтому, если неравенство выполняется для некоторых i, оно также справедливо и для i = j - 1).

Итак, у вас есть только линейная проверка: вам нужно проверить, верно ли хотя бы для одного j A[j-1] + A[j] > A[j+1].

Всего O(N log N) {sorting} + O(N) {check} = O(N log N).

---

Обращаясь к комментарию об отрицательных числах: действительно, это то, что я не учел в исходном решении. Учет отрицательных чисел не сильно меняет решение, так как никакое отрицательное число не может быть частью треугольной тройки . Действительно, если A[i], A[j] и A[k] образуют треугольную тройку, то A[i] + A[j] > A[k], A[i] + A[k] > A[j], что подразумевает 2 * A[i] + A[j] + A[k] > A[k] + A[j], следовательно, 2 * A[i] > 0, поэтому A[i] > 0 и по симметрии A[j] > 0, A[k] > 0.

Это означает, что мы можем безопасно удалить отрицательные числа и нули из последовательности, что делается в O(log n) после сортировки.

Answer 2

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

Вот реализация алгоритма, предложенного Владом. Теперь вопрос требует предотвращения переполнения, поэтому приведение к 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 4

Вот простое решение в java со счетом 100/100

class Solution {
  public int solution(int[] A) {
    // write your code in Java SE 8
    Arrays.sort(A);
    for (int i = 0; i < A.length - 2; ++i) {
      long a = A[i] + (long) A[i + 1];
      long b = A[i + 2];
      if (a > b) {
        return 1;
      }
    }
    return 0;
  }
}

Answer 5

Сначала сделайте быструю сортировку, обычно это займет nlogn.И вы можете пропустить третий цикл с помощью бинарного поиска, который может занять log (n).Таким образом, сложность сводится к n ^ 2log (n).

Answer 6

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;

}

Вышеуказанная реализация является линейной по временной сложности.Идея проста - использовать формула, которую они дали, извлекая серию триплетов отсортированных элементов.

Answer 7

Вот мое решение в C #, которое получает 90% правильности (неправильный ответ возвращается для теста extreme_arith_overflow1 -overflow test, 3 MAXINTs-) и 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 8

Мне кажется, что для меня проще изменить цикл решения Влада.

Уравнение A [j-1] + A [j]> A [j + 1] можно изменить на A [K-2] + A [K-1]> A [K].Объяснено словами, сумма последних двух самых больших чисел должна быть больше, чем текущее наибольшее значение, которое проверяется (A [k]).Если результат сложения двух последних больших чисел (A [k-2] и A [k-1]) не больше, чем A [k], мы можем перейти к следующей итерации цикла.

Кроме того, мы можем добавить проверку на отрицательные числа, о которой говорил Влад, и остановить цикл ранее.

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

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

У меня есть другое решение для подсчета треугольников.Его временная сложность составляет O (N ** 3) и занимает много времени для обработки длинных массивов.

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