如何知道我们阵列中存在三角形三元组？ [英] How to know that a triangle triple exists in our array?

问题描述

 <$ c $ 
 
 c> int triangle（int [] A）; 
  

给出一个零索引数组A，其中包含 N 0< $ c>整数，则返回 1 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 
  （0,2,4） code>满足所有必需的条件。
 
 
对于数组 A ，例如
  A [0] = 10，A [1] = 50，A [2] = 5，A [3] = 1 
  
函数应该返回 0 。
 
 
 
如果我做一个三重循环，这会非常慢（复杂度： O（n ^ 3））。我想也许用来存储数组的额外副本并对其进行排序，并使用二进制搜索特定数字。但我不知道如何分解这个问题。
 
有什么想法吗？
     所有，你可以排序你的序列。对于排序的序列，足以检查 A [i] + A [j]> A [k] 用于 i < j< k ，因为 A [i] + A [k]> A [k]> A [j] 等等，所以其他两个不等式自动成立。
 
 
 
（从现在开始， i ） $ b 
接下来，检查 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）{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）排序后。
 
I was stuck in solving the following interview practice question:

I have to write a function:
int triangle(int[] A);
that given a zero-indexed array A consisting of N integers returns 1 if there exists a triple (P, Q, R) such that 0 < P < Q < R < N.
A[P] + A[Q] > A[R],  
A[Q] + A[R] > A[P],  
A[R] + A[P] > A[Q].
The function should return 0 if such triple does not exist. Assume that 0 < N < 100,000. Assume that each element of the array is an integer in range [-1,000,000..1,000,000].

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, because the triple (0, 2, 4) fulfills all of the required conditions.

For array A such that
A[0]=10, A[1]=50, A[2]=5, A[3]=1
the function should return 0.

If I do a triple loop, this would be very very slow (complexity: O(n^3)). I am thinking maybe to use to store an extra copy of the array and sort it, and use a binary search for a particular number. But I don't know how to break down this problem.

Any ideas?
解决方案
First of all, you can sort your sequence. For the sorted sequence it's enough to check that A[i] + A[j] > A[k] for i < j < k, because A[i] + A[k] > A[k] > A[j] etc., so the other 2 inequalities are automatically true.

(From now on, i < j < k.)

Next, it's enough to check that A[i] + A[j] > A[j+1], because other A[k] are even bigger (so if the inequality holds for some k, it holds for k = j + 1 as well).

Next, it's enough to check that A[j-1] + A[j] > A[j+1], because other A[i] are even smaller (so if inequality holds for some i, it holds for i = j - 1 as well).

So, you have just a linear check: you need to check whether for at least one j A[j-1] + A[j] > A[j+1] holds true.

Altogether O(N log N) {sorting} + O(N) {check} = O(N log N).



Addressing the comment about negative numbers: indeed, this is what I didn't consider in the original solution. Considering the negative numbers doesn't change the solution much, since no negative number can be a part of triangle triple. Indeed, if A[i], A[j] and A[k] form a triangle triple, then A[i] + A[j] > A[k], A[i] + A[k] > A[j], which implies 2 * A[i] + A[j] + A[k] > A[k] + A[j], hence 2 * A[i] > 0, so A[i] > 0 and by symmetry A[j] > 0, A[k] > 0.

This means that we can safely remove negative numbers and zeroes from the sequence, which is done in O(log n) after sorting.

                        
这篇关于如何知道我们阵列中存在三角形三元组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！