给定
n一个数组中的正实数，找出这个集合中是否存在三元组，使得三元组的和在 范围内(1, 2)。在线性时间和恒定空间中进行。
- 数组没有排序。
- 数字是正数
- 数字是实数
任何帮助将不胜感激。谢谢。
问问题
18573 次
8 回答
51
诀窍是找出一种方法来对可能的解决方案进行分类，并为每个解决方案提出一个线性时间常数空间解决方案。
考虑三个范围X = (0,2/3), Y = [2/3,1], Z = (1,2)。最多可以来自一个值Z（如果两个值来自Z，则总和将超过1+1=2）。同样，至少一个值必须来自X。假设有 3 个值a <= b <= c，因此1 <= a+b+c <= 2. 然后，考虑哪些可能的解决方案类别是可行的：
A) `a \in X, b \in X, C \in X`
B) `a \in X, b \in X, C \in Y`
C) `a \in X, b \in X, C \in Z`
D) `a \in X, b \in Y, C \in Y`
E) `a \in X, b \in Y, C \in Z`
那么我们如何测试每个案例呢？
案例 A 非常容易测试：总和保证低于 2，因此我们只需要测试最大总和（X 中最大的 3 个元素）是否超过 1。
案例 C 非常容易测试：因为保证总和大于 1，我们只需要检查总和是否低于 2。因此，为了做到这一点，我们只需要测试 X 中最小的 2 值和Z 中的最小值
情况 D 和 E 与 C 类似（因为总和必须至少为 4/3 > 1，所以在每个类别中选择最小的可能值）。
案例 B 是唯一棘手的案例。 0 < a+b < 4/3和2/3 <= c <= 1。为了处理案例 B，我们考虑这些区间：X1 = (0, 1/2), X2 = [1/2 2/3), Y = [2/3, 1]。
这导致以下三种有效情况：
B1。X1中的a，X2中的b，Y中的c
B2。X1中的a，X1中的b，Y中的c
B3。X2中的a，X2中的b，Y中的c
案例 B1 和 B3：三个数字的总和总是大于 1，所以我们取最小值并检查它是否小于 2。
案例B2：三个数字的和总是小于2，所以我们取最大和并检查是否大于1。
总而言之，测试是：
|X| >= 3和Xmax(1) + Xmax(2) + Xmax(3) >= 1|X| >= 2,|Z| >= 1, 和Xmin(1)+Xmin(2)+Zmin(1) <= 2|X| >= 1,|Y| >= 2, 和Xmin(1)+Ymin(1)+Ymin(2) <= 2|X| >= 1,|Y| >= 1,|Z| >= 1和Xmin(1)+Ymin(1)+Zmin(1) <= 2|X| >= 2,|Y| >= 1, 和Xmax(1) + Xmax(2) + Ymin(1) < 2|X| >= 2,|Y| >= 1, 和Xmin(1) + Xmin(2) + Ymax(1) > 1)
每次测试都可以在线性时间和常数空间中进行（只需要 find Xmax(1), Xmax(2), Xmax(3), Xmin(1), Xmin(2), Ymin(1), Ymin(2), Ymax(1), Zmin(1)，即使数据没有排序也可以一次性找到）
于 2013-10-24T06:43:43.647 回答
5
因此，您有一个长度为 n 的双精度数据类型数组。将三个变量 a、b 和 c 初始化为数组的前 3 个值。现在，从 i = 3 迭代到 n 并检查以下内容：1）检查 sum 是否在 (1, 2) 中，如果它确实返回 true。2)如果不是，则检查sum是否大于2，如果是，则将MAX(a,b,c)替换为当前元素arr[i]。3）否则总和必须小于1，然后将MIN（a，b，c）替换为当前元素arr [i]。最后在退出循环后再次检查最后一个三元组，如果总和落在（1,2）然后返回真，否则返回假。
enter code here
double a=arr[0], b=arr[1], c=arr[2];
for(int i=3 ; i<n ; i++){
// check if sum fall in (1, 2)
if(a+b+c > 1 && a+b+c < 2){
return 1;
}
// if not, then check is sum greater than 2
// if so, then replece MAX(a,b,c) to new number
else if(a+b+c > 2){
if(a>b && a>c){
a = arr[i];
}
else if(b>a && b>c){
b = arr[i];
}
else if(c>a && c>b){
c = arr[i];
}
}
// else then sum must be less than 1
// then replace MIN(a,b,c) to new number
else{
if(a<b && a<c){
a = arr[i];
}
else if(b<a && b<c){
b = arr[i];
}
else if(c<a && c<b){
c = arr[i];
}
}
}
// check for last a, b, c triplet
if(a+b+c > 1 && a+b+c < 2){
return 1;
}
else{
return 0;
}
于 2018-06-06T20:33:00.563 回答
5
问的问题类似于这个 InterviewBit问题。我对下面提到的解决方案进行了一些更改，以完全符合您的要求。
有以下三个条件：
- 首先，如果总和在 1 和 2 之间。
- 其次，如果总和大于 2，则将三个中较大的元素替换为下一个元素，并重复该过程。
- 第三，如果总和小于 1，则将三个中较小的元素替换为下一个元素，并重复相同的过程。
int Solution::solve(vector<float> &A) {
if(A.size()<3) return 0;
float a = A[0];
float b = A[1];
float c = A[2];
for(int i=3;i<A.size();++i){
if(a+b+c>1 && a+b+c<2)
return 1;
float temp = A[i];
if(a+b+c>=2){
if(a>b && a>c)
a = temp;
else if(b>c && b>a)
b = temp;
else
c = temp;
}
else{
if(a<b && a<c)
a = temp;
else if(b<c && b<a)
b = temp;
else
c = temp;
}
}
if(a+b+c>1 && a+b+c<2) return 1;
return 0;
}
同样的问题也可以使用两个指针技术来解决。首先，我们必须对数组进行排序。但是，它的复杂性将超过 O(logn)。
int Solution::solve(vector<float> &A) {
int n = A.size();
if(n<3) return 0;
sort(A.begin(), A.end());
int l = 0, r = n-1;
while(l<r-1){
float s = A[l]+A[l+1]+A[r];
if(s>=2)
r = r-1;
else if(s<1)
l = l+1;
else return 1;
}
return 0;
}
于 2020-06-14T12:20:32.667 回答
2
使用滑动窗口求和方法可以在线性运行时间内轻松解决此问题。在这种情况下，我们将使用大小为 3 的窗口。这也称为“移动和算法”。
下面的算法
1> Prepare the window of size 3 with the first 3 elements
2> IF (array.len <= 3): CHECK IF window-sum is in the range (1,2), then RETURN accordingly
3> FOR i = 3 UPTO (array.len-1)
3.1> SORT the window (3log3 = constant time operation)
3.2> IF window-sum is in the range (1,2): RETURN 1 or TRUE
3.3> ELSE IF window-sum < 1: Replace the smallest element in the window (window[0]) with array[i]
3.4> ELSE IF window-sum > 2: Replace the largest element in the window (window[2]) with array[i]
4> Outside the loop, check the FINAL window sum and RETURN accordingly.
在此处访问 Python 代码。请给存储库加星标！
于 2019-12-08T14:38:43.960 回答
0
@soul Ec 给出的解决方案的 Java 代码。
我们需要修改案例 B。假设我们的数字是 a+b+c
there are three ranges
x1 x2 y
(0,1/2) (1/2,2/3) (2/3,1)
we have 4 possibilities
1. x1 + x1 +y
2. x2 + x2 +y
3. x1 + x2 +y
4 x2 + x1 +y
这里情况 3 和 4 是相同的，因为它的总和是相同的。所以我们只有3个案例。
1. x1 + x1 + y it is always <2 ( do x1max+x1max+ymax <2 to verify)
so we have to check if x1max(1)+x1max(2)+ymax(1) > 1
2. x2 + x2 + y it is always >1 ( do x2min+x2min+ymin >1 to verify)
so we have to check if x2min(1)+x2min(2)+ymin(1) <=2
3. x1 + x2 + y it is always >1 (do x1min+x2min+ymin >1 to verify)
so we have to check if x1min(1)+x2min(1)+ymin(1)<=2
public static int solve(ArrayList<String> A) {
double d[]= new double[A.size()];
for(int i=0;i<A.size();i++) {
d[i]= Double.parseDouble(A.get(i));
}
double range1 = 0;
double range2 = (double) 2/3;
double range3 = 1;
double range4 = 2;
double range02 =(double) 1/2;
// min and max in range (0,2/3)
double min1= Double.MAX_VALUE;
double min2=Double.MAX_VALUE;
double min3=Double.MAX_VALUE;
double max1= Double.MIN_VALUE;
double max2=Double.MIN_VALUE;
double max3=Double.MIN_VALUE;
// min and max in range (2/3,1)
double miny1= Double.MAX_VALUE;
double miny2=Double.MAX_VALUE;
double miny3=Double.MAX_VALUE;
double maxy1= Double.MIN_VALUE;
double maxy2=Double.MIN_VALUE;
double maxy3=Double.MIN_VALUE;
// min and max in range (1,2)
double minz1= Double.MAX_VALUE;
double minz2=Double.MAX_VALUE;
double minz3=Double.MAX_VALUE;
double maxz1= Double.MIN_VALUE;
double maxz2=Double.MIN_VALUE;
double maxz3=Double.MIN_VALUE;
// min and max in range (0,1/2)
double minxx1= Double.MAX_VALUE;
double minxx2=Double.MAX_VALUE;
double minxx3=Double.MAX_VALUE;
double maxx1= Double.MIN_VALUE;
double maxx2=Double.MIN_VALUE;
double maxx3=Double.MIN_VALUE;
// min and max in range (1/2,2/3)
double minyy1= Double.MAX_VALUE;
double minyy2=Double.MAX_VALUE;
double minyy3=Double.MAX_VALUE;
double maxyy1= Double.MIN_VALUE;
double maxyy2=Double.MIN_VALUE;
double maxyy3=Double.MIN_VALUE;
for (int i = 0; i < d.length; i++) {
if (d[i] >= range1 && d[i] < range02) {
if (d[i] < minxx3) {
minxx1=minxx2;
minxx2=minxx3;
minxx3 = d[i];
} else if (d[i] > minxx3 && d[i] < minxx2) {
minxx1=minxx2;
minxx2 = d[i];
} else if (d[i] > minxx3 && d[i] > minxx2 && d[i] < minxx1) {
minxx1 = d[i];
}
if (d[i] > maxx3) {
maxx1=maxx2;
maxx2=maxx3;
maxx3 = d[i];
} else if (d[i] < maxx3 && d[i] > maxx2) {
maxx1=maxx2;
maxx2 = d[i];
} else if (d[i] < maxx3 && d[i] < maxx2 && d[i] > maxx1) {
maxx1 = d[i];
}
}
if (d[i] >= range02 && d[i] < range2) {
if (d[i] < minyy3) {
minyy1=minyy2;
minyy2=minyy3;
minyy3 = d[i];
} else if (d[i] > minyy3 && d[i] < minyy2) {
minyy1=minyy2;
minyy2 = d[i];
} else if (d[i] > minyy3 && d[i] > minyy2 && d[i] < minyy1) {
minyy1 = d[i];
}
if (d[i] > maxyy3) {
maxyy1=maxyy2;
maxyy2=maxyy3;
maxyy3 = d[i];
} else if (d[i] < maxyy3 && d[i] > maxyy2) {
maxyy1=maxyy2;
maxyy2 = d[i];
} else if (d[i] < maxyy3 && d[i] < maxyy2 && d[i] > maxyy1) {
maxyy1 = d[i];
}
}
if (d[i] >= range1 && d[i] < range2) {
if (d[i] < min3) {
min1=min2;
min2=min3;
min3 = d[i];
} else if (d[i] > min3 && d[i] < min2) {
min1=min2;
min2 = d[i];
} else if (d[i] > min3 && d[i] > min2 && d[i] < min1) {
min1 = d[i];
}
if (d[i] > max3) {
max1=max2;
max2=max3;
max3 = d[i];
} else if (d[i] < max3 && d[i] > max2) {
max1=max2;
max2 = d[i];
} else if (d[i] < max3 && d[i] < max2 && d[i] > max1) {
max1 = d[i];
}
}
if (d[i] >= range2 && d[i] < range3) {
if (d[i] < miny3) {
miny1=miny2;
miny2=miny3;
miny3 = d[i];
} else if (d[i] > miny3 && d[i] < miny2) {
miny1=miny2;
miny2 = d[i];
} else if (d[i] > miny3 && d[i] > miny2 && d[i] < miny1) {
miny1 = d[i];
}
if (d[i] > maxy3) {
maxy1=maxy2;
maxy2=maxy3;
maxy3 = d[i];
} else if (d[i] < maxy3 && d[i] > maxy2) {
maxy1=maxy2;
maxy2 = d[i];
} else if (d[i] < maxy3 && d[i] < maxy2 && d[i] > maxy1) {
maxy1 = d[i];
}
}
if (d[i] >= range3 && d[i] <= range4) {
if (d[i] < minz3) {
minz1=minz2;
minz2=minz3;
minz3 = d[i];
} else if (d[i] > minz3 && d[i] < minz2) {
minz1=minz2;
minz2 = d[i];
} else if (d[i] > minz3 && d[i] > minz2 && d[i] < minz1) {
minz1 = d[i];
}
if (d[i] > maxz3) {
maxz1=maxz2;
maxz2=maxz3;
maxz3 = d[i];
} else if (d[i] < maxz3 && d[i] > maxz2) {
maxz1=maxz2;
maxz2 = d[i];
} else if (d[i] < maxz3 && d[i] < maxz2 && d[i] > maxz1) {
maxz1 = d[i];
}
}
}
if(max1+max2+max3>=1 && max1!=Double.MIN_VALUE && max2!=Double.MIN_VALUE && max3!=Double.MIN_VALUE)
return 1;
if(min3+min2+minz3<=2 && min3!=Double.MAX_VALUE && min2!=Double.MAX_VALUE && minz3!=Double.MAX_VALUE )
return 1;
if(min3+miny3+miny2<=2 && min3!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE && miny2!=Double.MAX_VALUE)
return 1;
if(min3+miny3+minz3<=2 && min3!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE && minz3!=Double.MAX_VALUE)
return 1;
if(maxx3+maxx2+maxy3>1 && maxx3!=Double.MIN_VALUE && maxx2!=Double.MIN_VALUE && maxy3!=Double.MIN_VALUE) {
return 1;
}
if(minyy3+minyy2+miny3<=2 && minyy3!=Double.MAX_VALUE && minyy2!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE) {
return 1;
}
if(minxx3+minyy3+miny3<=2 && minxx3!=Double.MAX_VALUE && minyy3!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE) {
return 1;
}
return 0;
}
于 2019-05-10T11:48:45.100 回答
0
解决方案在 C++ 中（interviewbbit 解决方案）
int Solution::solve(vector<string> &arr) {
int n=arr.size(),i;
vector<float>v;
for(i=0;i<n;i++)
{
v.push_back(stof(arr[i]));
}
float a=v[0],b=v[1],c=v[2];
float mx=0;
for(i=3;i<n;i++)
{
if(a+b+c<2 && a+b+c>1)
return 1;
else if(a+b+c>2)
{
if(a>b && a>c)
a=v[i];
else if(b>a && b>c)
b=v[i];
else
c=v[i];
}
else
{
if(a<b && a<c)
a=v[i];
else if(b<a && b<c)
b=v[i];
else
c=v[i];
}
}
if(a+b+c>1 && a+b+c<2)
return 1;
else
return 0;
}
于 2019-07-15T13:49:20.690 回答
-3
我们可以很容易地在 O(n) 中做到这一点，我们只需要找到三个最小的正实数，我们可以在一次迭代中找到它们，最后如果它们的总和在 (1,2) 之间，则返回 1 否则返回 0 .
于 2019-10-04T14:24:48.523 回答