如何知道我们的数组中存在三角形三元组?
我一直在解决以下面试练习题:
我要写一个函数:
I was stuck in solving the following interview practice question:
I have to write a function:
int triangle(int[] A);
如果存在一个三元组 (P, Q, R) 使得 0 <P＜Q
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].
如果这样的三元组不存在，该函数应该返回 0.假设 0 <N＜100,000.假设数组的每个元素都是 [-1,000,000..1,000,000] 范围内的整数.
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].
例如，给定数组 A 使得
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
函数应该返回 1，因为三元组 (0, 2, 4) 满足所有要求的条件.
the function should return 1, because the triple (0, 2, 4) fulfills all of the required conditions.
对于数组A这样
A[0]=10, A[1]=50, A[2]=5, A[3]=1
函数应该返回0.
如果我做一个三重循环，这将非常非常慢(复杂性:O(n^3)).我在想也许可以用来存储数组的额外副本并对其进行排序，并对特定数字使用二进制搜索.但我不知道如何解决这个问题.
有什么想法吗?
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?
推荐答案
首先，你可以对你的序列进行排序.对于排序序列，检查 A[i] + A[j] > 就足够了.A[k] for i j＜k，因为 A[i] + A[k] >A[k]＞A[j] 等，所以其他 2 个不等式自动为真.
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.
(从现在开始，i
接下来，检查 A[i] + A[j] > 就足够了.A[j+1]，因为其他的 A[k] 更大(所以如果不等式对某些 k 成立，它对 成立k = j + 1).
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).
接下来，检查 A[j-1] + A[j] > 就足够了.A[j+1]，因为其他 A[i] 甚至更小(所以如果不等式适用于某些 i，它适用于 i= j - 1).
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).
所以，你只有一个线性检查:你需要检查是否至少有一个 j A[j-1] + A[j] >A[j+1] 成立.
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.
总共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.
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.
这意味着我们可以安全地从序列中删除负数和零，这是在排序后在 O(log n) 中完成的.
This means that we can safely remove negative numbers and zeroes from the sequence, which is done in O(log n) after sorting.
相关文章