如何知道陣列中存在三角形三元組？

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提取一系列三元組的分類元素。