Учитывая
nположительные действительные числа в массиве, найдите, существует ли триплет среди этого множества такое, что сумма триплета находится в диапазоне(1, 2). Делайте это в линейном времени и в постоянном пространстве.
- массив не упорядочен.
- цифры положительные
- цифры действительные числа
Любая помощь будет принята с благодарностью. Спасибо.
Хитрость заключается в том, чтобы определить способ классифицировать возможные решения и придумать линейное решение постоянного пространства для каждого.
Рассмотрим три диапазона 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, поэтому нам просто нужно проверить наибольшую сумму (наибольшие 3 элемента в X) превышает 1.
Случай C невероятно прост в тестировании: поскольку сумма гарантированно выше 1, нам нужно только проверить, равна ли сумма ниже 2. Поэтому для этого нам просто нужно проверить наименьшие 2 значения в X и наименьшее значение в Z
Случаи D и E аналогичны C (так как сумма должна быть не менее 4/3 > 1, выберите наименьшие возможные значения в каждом классе).
Случай B - единственный сложный случай. 0 < a+b < 4/3 и 2/3 <= c <= 1. Для обработки случая В рассмотрим эти интервалы: X1 = (0, 1/2), X2 = [1/2 2/3), Y = [2/3, 1].
Это приводит к следующим трем действительным случаям:
B1. a в X1, b в X2, c в Y
В2. a в X1, b в X1, c в Y
B3. a в X2, b в X2, c в Y
Случай 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)Каждый тест может выполняться в линейном времени и постоянном пространстве (вам нужно только найти Xmax(1), Xmax(2), Xmax(3), Xmin(1), Xmin(2), Ymin(1), Ymin(2), Ymax(1), Zmin(1), все из которых можно найти за один проход, даже если данные не отсортированы)
Итак, у вас есть массив двойных типов данных длины n. Запустите три переменные a, b и c как первые 3 значения массива. Теперь выполните итерацию от я = 3 до n и проверьте следующее: 1) Проверьте, попадает ли сумма в (1, 2), и возвращает ли она значение true. 2) Если нет, то проверьте, является ли сумма больше 2, если так, то замените MAX (a, b, c) на текущий элемент arr [i]. 3) В противном случае сумма должна быть меньше 1, затем заменить MIN (a, b, c) на текущий элемент arr [i]. И, наконец, после выхода из цикла еще раз проверить последний триплет, если сумма попадает в (1,2), то вернуть true, иначе вернуть false.
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;
}
Основываясь на идеях @Soul Ec, это код, который я придумал. Работает отлично.
vector<double> x;
vector<double> y;
vector<double> z;
double d = (double)2/3;
for(i = 0 ; i < arr.size() ; i++){
if(arr[i] >= 0 && arr[i] < d) x.push_back(arr[i]);
else if(arr[i] >= d && arr[i] <= 1) y.push_back(arr[i]);
else z.push_back(arr[i]);
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
sort(z.begin(), z.end());
int xsz = x.size();
int ysz = y.size();
int zsz = z.size();
if(xsz >= 3 && x[xsz-1] + x[xsz-2] + x[xsz-3] >= 1.0) return 1;
if(xsz >= 2 && zsz >= 1 && x[0] + x[1] + z[0] <= 2.0) return 1;
if(xsz >= 1 && ysz >= 2 && x[0] + y[0] + y[1] <= (double)2.0) return 1;
if(xsz >= 1 && ysz >= 1 && zsz >= 1 && x[0] + y[0] + z[0] <= 2.0) return 1;
if(xsz >= 2 && ysz >= 1){
if(x[xsz-1] + x[xsz-2] + y[0] < 2.0 && x[xsz-1] + x[xsz-2] + y[0] > 1.0) return 1;
if(x[0] + x[1] + y[ysz-1] > 1.0 && x[0] + x[1] + y[ysz-1] < 2.0) return 1;
}
Java-код для решения, заданного @soul Ec.
нам нужно изменить случай B. допустим, наши числа являются + 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;
}
решение находится в c++ (интервью-битное решение)
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;
}
Мы можем легко сделать это в O (n), нам просто нужно найти три минимальных положительных действительных числа, которые мы можем найти за одну итерацию, и в конце концов, если их суммирование лежит между (1,2), то вернуть 1, иначе вернуть 0 ,
Проблема в целом, как указано, неразрешима. Это связано с тем, что для любых двух действительных чисел a и b не может быть принято решение, если a > b выполняется (см. Также этот ответ), Но для решения этой проблемы вам нужно выполнить хотя бы одно сравнение реального числа с целым значением. Сравнение с целым числом не облегчает задачу, так как у вас может быть реальное число, которое 2,00...001, где между цифрами 2 и 1 имеется произвольное количество нулей, которое вы не знаете заранее. Сохранение таких реальных чисел (возможно, не всех, но многих из них) в основной памяти компьютера не является большой проблемой для таких конкретных, поскольку они могут быть представлены алгоритмом аппроксимации.
для получения дополнительной информации я предлагаю прочитать Теория сложности реальных функций