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

问题描述

我一直在解决以下面试练习题:
我要写一个函数:

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.

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