从数组中找到三角形 [英] finding triangulars from array

问题描述

零索引数组A由N个整数组成。三元组（P，Q，R）是三角形的if和

  A [P] + A [Q] A [R]，
 A [Q] + A [R] A [P]，
 A [R] + A [P] A [Q]。 
  

例如，假设数组A使

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

三合一（0,2,4）是三角形。
编写函数

  int triangle（const vector< int>& A）; 
  

假设一个由N个整数组成的零索引数组A，

假设：

N是范围内的整数[ 0..100,000];
数组A的每个元素是范围[-2,147,483,648..2,147,483,647]内的整数。
例如，给定数组A，使得

A [0] = 10 A [1] = 2 A [2] = 5
[3] = 1 A [4] = 8 A [5] = 20
该函数应返回1，如上所述。给定数组A，使得
A [0] = 10 A [1] = 50 A [2] = 5
A [3] = 1
函数应该返回0.
预期最坏情况时间复杂度：

预期最坏情况下的空间复杂度：O（1）

解决方案

如果 O（N³）是可接受的时间复杂度，则下面的伪代码应该工作。

  for（P in A）{
对于（A中的Q）{
对于（R中A）{
如果（A [P]> 0& A [Q]> 0&如果（A [P]> A [R] -A [Q]& A [Q]> A [P] -A [R]& A [R]> A [Q] -A [P]）{
 return 1; 
} 
} 
} 
} 
} 
 return 0; 
  

if语句的原因是：

因为int可以是任何max到int你必须处理溢出。将它们添加在一起可能会导致奇怪的错误，如果在数组中有两个非常大的int。所以，我们测试他们是否为正，然后重写公式做相同的检查，但与减法。如果任何值为负或0，我们不需要做任何事情，因为：

 假设x <= 0 
假设x + y> z 
假设x + z> y 
然后y> z和z> y是一个矛盾
  

因此没有负值或零值int将是三元组的一部分

zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if and

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

For example, consider array A such that

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

Triplet (0, 2, 4) is triangular. Write a function

int triangle(const vector<int> &A);

that, given a zero-indexed array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

Assume that:

N is an integer within the range [0..100,000]; each element of array A is an integer within the range [-2,147,483,648..2,147,483,647]. For example, given array A such that

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20 the function should return 1, as explained above. Given array A such that A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1 the function should return 0. Expected worst-case time complexity:
Expected worst-case space complexity: O(1)

解决方案

If O(N³) is acceptable time complexity then the Pseudocode below should work. If you have stricter time complexity requirements then you'll have to specify them.

for (P in A){
    for (Q in A){
        for (R in A){
            if(A[P] > 0 && A[Q] > 0 && A[R] > 0){
                if(A[P] > A[R] - A[Q] && A[Q] > A[P] - A[R] && A[R] > A[Q] - A[P]){
                    return 1;
                }
            }
        }
    }
}
return 0;

The reasoning behind the if statements is this:

Since the ints can be anything up to max int you have to deal with overflow. Adding them together could cause a weird error if there are two very large ints in the array. So instead we test if they are positive and then rewrite the formulae to do the same checks, but with subtraction. We don't need to do anything if any of the values are negative or 0, since:

Assume x <= 0
Assume x+y > z
Assume x+z > y
Then y > z and z > y which is a contradiction

So no negative or zero valued ints will be a part of a triple

这篇关于从数组中找到三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！