如何知道我们的数组中存在三角形三元组？

Question

我被困在解决以下面试练习问题中：
我必须编写一个函数：

int triangle(int[] A);

给定一个由 N 个整数组成的零索引数组 A，如果存在一个三元组（P、Q、R），使得 1 则返回 1代码>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

我有另一种解决方案来计算三角形。其时间复杂度为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

Answer 2

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 3

对我来说，反转 Vlad 解决方案的循环似乎更容易理解。

等式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]，我们可以进入循环的下一次迭代。

另外，我们可以添加 Vlad 提到的对负数的检查，并提前停止循环。

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 4

这是我在 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 5

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 6

100% Swift 解决方案：

public func solution(_ A : inout [Int]) -> Int {
    guard A.count > 2 else { return 0 }
    A.sort()

    for i in 2..<A.count {
        if A[i - 2] + A[i - 1] > A[i] {
            return 1
        }
    }
    return 0
}

Answer 7

在 ruby​​ 中，

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

只需将其移植为您选择的语言即可

Answer 8

在爪哇中：

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 9

这是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 10

这是 Vlad 提出的算法的实现。现在的问题需要避免溢出，因此需要强制转换为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 11

首先进行快速排序，这通常需要 nlogn。
并且可以通过二分查找省略第三个循环，该循环可以取 log(n)。
总而言之，复杂度降低到n^2log(n)。

Answer 12

100/100 php 解决方案： http:// www.rationalplanet.com/php-lated/maxproductof Three-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 13

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

排序：对数线性复杂度 O(N log N)

Answer 14

首先，您可以对顺序进行排序。对于排序序列，检查 A[i] + A[j] > 就足够了。 A[k] 对于 i j＜ k，因为 A[i] + A[k] > A[k]＞ A[j] 等，因此其他 2 个不等式自动成立。

（从现在开始，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) {排序} + O(N) {检查} = 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) 时间内完成。