如何知道阵列中存在三角形三元组？

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]等等，所以其他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以及）。

因此，您只需进行线性检查：您需要检查是否至少有一个jA[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

先做一个快速排序，这通常需要nlogn。 你可以省略第二个循环的二分搜索，它可以采取log（n）。所以总的来说，复杂度降低到n^2log（n）。

Answer 3

在红宝石怎么样

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 4

这里的语言是弗拉德提出的算法的实现。现在的问题需要避免溢出，因此需要转换为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

在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

甲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 

排序：对数线性复杂性O（N日志N ）

Answer 8

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

扭转了弗拉德液循环，我似乎更容易理解。可以将等式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 11

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

} 

上面实现是线性的时间复杂度。这个概念很简单，用他们提供的formaula提取一系列三元组的分类元素。