1

给定n一个n正整数数组，需要有多少种方法可以选择三个数字以使它们不能形成三角形。

例子： 

3  
4 2 10

回答： 

1

我的方法（在JAVA）

int[] arr = new int[n];//list of the numbers given
int count=0;//count of all such triplets
for(int i=0;i<n;i++)
    arr[i]=sc.nextInt();
Arrays.sort(arr);
for(int i=n-1;i>=0;i--)
{
    int j=0;
    int k= i-1;
     while(j<k && k>=0)
     {
         if(arr[i]>=arr[j]+arr[k])//condition for no triangle formation
          {
              count++;
              j++;//checking the next possible triplet by varying the third number
          }
          else if(arr[i]<arr[j]+arr[k])
          {
              j=0;
              k--;//now varying the second number if no such third number exists
          }
     }
}
System.out.println(count);

我的算法：

在对列表进行排序后，我试图找到小于 的所有数字，在arr[i]这种arr[i]>=arr[j]+arr[k]情况下，不会形成三角形。

但我正在接受timed-out这个解决方案。任何人都可以提出更好的方法来解决这个问题吗？

4

2 回答 2

3

适当的伪代码是：

SORT array //nlogn
INT counter = n*(n-1)*(n-2)/6;
FOR i = n - 1; i >= 2; i-- DO //largest length in a triangle - there must be two lower
    currentLargestNumber = array[i];
    FOR j = i - 1; j >= 1; j-- DO
        BINARY SEARCH FOR SMALLEST k for which array[k] + array[j] > array[i]
        counter -= j - k;
        IF nothingAddedInTheLastIteration DO
            BREAK;
        END_IF
    END_FOR
    IF nothingAddedInTheLastIteration DO
        BREAK;
    END_IF
END_FOR

我假设不会有超过 3 个相同值的输入。如果存在这种可能性，请删除不必要的值。

在每个循环中，您应该检查是否添加了任何三角形。如果没有，请打破这个循环。

于 2016-08-17T08:30:37.027 回答
1

这个问题可以使用两个指针技术来解决，但不是计算有多少三元组不能形成三角形，我们将寻找相反的结果，最后从 中减去结果C(n,3) = (n)(n-1)(n-2)/6。让我们对数组arr,进行排序arr[0] < arr[1] .. < arr[n-1]。并且对于给定的对i < j找到索引k > j， st arr[i] + arr[j] <= arr[k]和arr[i] + arr[j] > arr[k-1]。这将导致额外的k - j -1三元组（三元组是：{i,j,j+1},{i,j,j+2},..,{i,j,k-1}。现在请注意，每当我们增加时j，我们不需要重置 的值k，这有助于保持总时间复杂度O(n^2)。

//arr is already sorted
long triangles = 0;
for(int i = 0; i < n-2; i++){
   int k = i + 2;
   for(int j = i + 1; j < n; j++){
      while(arr[i] + arr[j] > arr[k] && k < n){
         k++;
      }
      triangles += k-j-1;
   }
} 
long answer = n*(n-1)*(n-2)/6 - triangles;
于 2016-08-17T09:02:21.697 回答