d****o
发帖数: 1055 | 1 You are given with three sorted arrays ( in ascending order), you are
required to find a triplet ( one element from each array) such that distance
is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then
distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
Please give a solution in O(n) time complexity | c*****e
发帖数: 737 | | z******w
发帖数: 36 | 3 a greedy approach with O(n) time complexity
1. get the first element of a, b and c. let's use x denotes the largest one,
y denotes medium one, z denotes the smallest one.
2. if the distance(x, y) > distance(y, z), move the y to the next number in
the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
if distance(x,y) == distance(y,z) move y and z together to the next number.
3. update the x,y,z with the new value and repeat the procedure above. | p********n
发帖数: 20 | 4 类似的一题：
Given n arrays, find n number such that sum of their differences is
minimum. For e.g. if there are three arrays
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here
the answer is a = 15, b = 13, and c = 14
方法应该是一样的 | d****o
发帖数: 1055 | 5 这个什么时候停？是不是需要记录一个minDistance？
比如
A= 1,2,3
B= 4,5,6
C= 7,8,9
按照这种方法，移到最后是
x=1
y=6
z=8
distance=7
但是最开始没移的时候distance=6
one,
in
【在 z******w 的大作中提到】
: a greedy approach with O(n) time complexity
: 1. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.
: 2. if the distance(x, y) > distance(y, z), move the y to the next number in
: the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
: if distance(x,y) == distance(y,z) move y and z together to the next number.
: 3. update the x,y,z with the new value and repeat the procedure above.
| d****o
发帖数: 1055 | 6 好像这道题的思路是这样的。（不知道和你的方法是不是最后的结果一样。没有怎么看
懂你的方法为什么）
假设
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
1. 初始化一个全局最小值minDistance=INT_MAX;当前距离curDistance=0;
2. get the first element of a, b and c. let's use x denotes the largest one,
y denotes medium one, z denotes the smallest one.(a=1,b=4,c=5)
3. 找到最小值a，最开始在B[0],那么我就一直把a往右移，直到a>b (13>4),假设移到
了B[i](这里i=1),计算 B[i]之前的一个数B[i-1](就是B[0])和最大值c的差,(c-B[0]=5
-1=4),这个差就是curDistance,如果curDistance小于minDistance,更新minDistance.
4. 更新a,b,c
5. 重复step 2,3,4，直到全部array已经移到了尾部。
one,
in
【在 z******w 的大作中提到】
: a greedy approach with O(n) time complexity
: 1. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.
: 2. if the distance(x, y) > distance(y, z), move the y to the next number in
: the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
: if distance(x,y) == distance(y,z) move y and z together to the next number.
: 3. update the x,y,z with the new value and repeat the procedure above.
| x*******5
发帖数: 152 | 7 The code: 欢迎验证
int Array::Find_value(vector a, vector b, vector c){
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
std::sort(c.begin(),c.end());
int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
int l=INT_MAX;
while(i
l=min(l,max(a[i]-b[j],max(b[j]-c[k],c[k]-a[i])));
if(a[i]<=b[j]&&a[i]<=c[k]) i++;
else if(b[j]<=a[i]&&b[j]<=c[k]) j++;
else if(c[k]<=a[i]&&c[k]<=b[j]) k++;
}
return l;
} | k*****y
发帖数: 744 | 8 考虑六种从小到大排列的可能情况，每种找出最小的distance，再一起比较。
import random
# generate random data
data = [[],[],[]]
for i in range(0,3):
N = random.randint(5, 10)
for j in range(0, N):
data[i].append(random.randrange(0, 1000))
data[i].sort()
test_cases = [(0,1,2), (0,2,1),
(1,0,2), (1,2,0),
(2,0,1), (2,1,0)]
pos = [[]]*len(test_cases)
dist = [1000000]*len(test_cases)
def LowerBound(x, queueID, start):
for i in range( start, len(data[queueID]) ):
if data[queueID][i] >= x:
return i
return len(data[queueID])
# test the case x <= y <= z with
# x in data[id[0]], y in data[id[1]], z in data[id[2]]
for case in range( 0, len(test_cases) ):
id0, id1, id2 = test_cases[case]
pos1, pos2 = 0, 0
for pos0 in range( 0, len(data[id0]) ):
x = data[id0][pos0]
pos1 = LowerBound(x, id1, pos1)
if pos1 < len(data[id1]):
y = data[id1][pos1]
pos2 = LowerBound(y, id2, pos2)
if pos2 < len(data[id2]):
z = data[id2][pos2]
if dist[case] >= z-x:
dist[case] = z-x
pos[case] = [pos0, pos1, pos2]
else:
break
else:
break
min_case = 0
for case in range( 1, len(test_cases) ):
if dist[case] < dist[min_case]:
min_case = case
print data[0];
print data[1];
print data[2];
q0, q1, q2 = test_cases[min_case]
pos0, pos1, pos2 = pos[min_case]
print 'the minimal distance is ', dist[min_case]
print 'queue ', q0, ' at ', pos0, ' with value ', data[q0][pos0];
print 'queue ', q1, ' at ', pos1, ' with value ', data[q1][pos1];
print 'queue ', q2, ' at ', pos2, ' with value ', data[q2][pos2];
distance
【在 d****o 的大作中提到】
: You are given with three sorted arrays ( in ascending order), you are
: required to find a triplet ( one element from each array) such that distance
: is minimum.
: Distance is defined like this :
: If a[i], b[j] and c[k] are three elements then
: distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
: Please give a solution in O(n) time complexity
| z****c
发帖数: 602 | 9 可以把三个数组merge到一个大数组中，同时要保留element from where
用三个变量记录most recent element from each array 从大数组的开始遍历，
假设当前数来自数组A，那么找到它到most recent B and most recent C的距离。然后
更新most recent A。
不知这样对不？ | l*****y
发帖数: 56 | 10 像楼主说的，每次把最小的往上移。
用了三个指针，分别指向三个数组，中间会交换指针，min, mid, max，他们分别指向
三个从小到到大排列的数， 距离就是 *max -*min.
最后return the minimal distance, the vector d records the three elements
with minimal distance.
请指正， 谢谢了！
void swap(vector::iterator &a, vector::iterator &b){
vector::iterator temp;
temp=a;
a=b;
b=temp;
}
int min_dist(vector &a, vector &b, vector &c, vector &d){
vector::iterator min=a.begin(), mid=b.begin(), max=c.begin();
int dist=100000; //Make the initial dist large enough.
for(int i=0; i<3; ++i)
{ d.push_back(0);}
while (min!= a.end() && min!= b.end() && min!=c.end()){
if (*min > *mid) swap(min, mid);
if (*mid > *max) swap(mid, max);
if (*min > *mid) swap(min, mid);
int t=*max - *min;
if (dist > t)
{
dist= t;
d[0]=*min;
d[1]=*mid;
d[2]=*max;
}
++min;
}
return dist;
}
【在 c*****e 的大作中提到】
: 每次总是移a,b,c中最小的一个？
| | | H*****1
发帖数: 4815 | 11 1，10， 40
2， 3， 19
5，80， 90
要找三个数的距离之和最小
答案应该是1,3,5
但这种办法不可能找到啊
one,
【在 d****o 的大作中提到】
: 好像这道题的思路是这样的。（不知道和你的方法是不是最后的结果一样。没有怎么看
: 懂你的方法为什么）
: 假设
: A = {4, 10, 15, 20}
: B = {1, 13, 29}
: C = {5, 14, 28}
: 1. 初始化一个全局最小值minDistance=INT_MAX;当前距离curDistance=0;
: 2. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.(a=1,b=4,c=5)
: 3. 找到最小值a，最开始在B[0],那么我就一直把a往右移，直到a>b (13>4),假设移到
| b***u
发帖数: 12010 | 12 不是找距离和最小，而是max。 125和135是一样的
【在 H*****1 的大作中提到】
: 1，10， 40
: 2， 3， 19
: 5，80， 90
: 要找三个数的距离之和最小
: 答案应该是1,3,5
: 但这种办法不可能找到啊
:
: one,
| b***u
发帖数: 12010 | 13 最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。 | b******v
发帖数: 1493 | 14 1, 2, 5也可以吧
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 H*****1 的大作中提到】
: 1，10， 40
: 2， 3， 19
: 5，80， 90
: 要找三个数的距离之和最小
: 答案应该是1,3,5
: 但这种办法不可能找到啊
:
: one,
| z*****n
发帖数: 447 | 15 每次把（X,Y，Z）中最小的往上移一位，计算一个min distance，得到一个新的（X，Y
，Z），重复以上步骤，最多一共 3N 次可以完成，O(N) | h*****y
发帖数: 218 | 16 这个应该好证明吧？
【在 b***u 的大作中提到】
: 最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。
| h*****y
发帖数: 218 | 17 每次移动最大的，只会让结果更大
移动中间的，最大的不会变
但是，不知道是否一定是全局最优解
大家能够给个证明么？
【在 h*****y 的大作中提到】
: 这个应该好证明吧？
| i***h
发帖数: 12655 | 18 这个不就是我前两天说的题么?
改头换面又出来了, 果然经典啊. | p*u
发帖数: 136 | 19 nice code!
【在 x*******5 的大作中提到】
: The code: 欢迎验证
: int Array::Find_value(vector a, vector b, vector c){
: std::sort(a.begin(),a.end());
: std::sort(b.begin(),b.end());
: std::sort(c.begin(),c.end());
: int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
: int l=INT_MAX;
: while(i: l=min(l,max(a[i]-b[j],max(b[j]-c[k],c[k]-a[i])));
: if(a[i]<=b[j]&&a[i]<=c[k]) i++;
| x*******5
发帖数: 152 | 20 证明也许比较难，但是我是这样做的：
/*Description: given three arrays A, B,C, find three indices i,j, k such that
the value l=max((a-b),(b-c), (c-a)) is minimized
Input: vector a, vector b, vector c
Output: void
K.O.: sorting, merge sort variant
*/
int Array::Find_value_brute(vector a, vector b, vector c){
int n=a.size(),m=b.size(),p=c.size(),l=INT_MAX;
for(int i=0;i
for(int j=0;j
for(int k=0;k
int ta=abs(a[i]-b[j]),tb=abs(b[j]-c[k]),tc=abs(c[k]-a[i]);
l=min(l,max(ta,max(tb,tc)));
}
return l;
}
int Array::Find_value(vector a, vector b, vector c){
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
std::sort(c.begin(),c.end());
int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
int l=INT_MAX;
while(i
int ta=abs(a[i]-b[j]),tb=abs(b[j]-c[k]),tc=abs(c[k]-a[i]);
l=min(l,max(ta,max(tb,tc)));
if(a[i]<=b[j]&&a[i]<=c[k]) i++;
else if(b[j]<=a[i]&&b[j]<=c[k]) j++;
else if(c[k]<=a[i]&&c[k]<=b[j]) k++;
}
return l;
}
提出的方法应该和brute force的结果一样，于是
int count=0;
for(int i=0;i<20000;i++){
vector a=Pearl::generate_int_swap(10,100);
vector b=Pearl::generate_int_knuth(10,200);
vector c=Pearl::generate_int_floyd(10,300);
int t1=Array::Find_value_brute(a,b,c);
int t2=Array::Find_value(a,b,c);
if (t1!=t2)
count++;
}
cout<
a,b,c是三个长度为10的随即数组，三个函数是我自己写的随即数生成器（idea来自编
程珠玑，所以namespace取的是Pearl）
多次实验，count都是0 | | | d****o
发帖数: 1055 | 21 You are given with three sorted arrays ( in ascending order), you are
required to find a triplet ( one element from each array) such that distance
is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then
distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
Please give a solution in O(n) time complexity | c*****e
发帖数: 737 | | z******w
发帖数: 36 | 23 a greedy approach with O(n) time complexity
1. get the first element of a, b and c. let's use x denotes the largest one,
y denotes medium one, z denotes the smallest one.
2. if the distance(x, y) > distance(y, z), move the y to the next number in
the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
if distance(x,y) == distance(y,z) move y and z together to the next number.
3. update the x,y,z with the new value and repeat the procedure above. | p********n
发帖数: 20 | 24 类似的一题：
Given n arrays, find n number such that sum of their differences is
minimum. For e.g. if there are three arrays
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here
the answer is a = 15, b = 13, and c = 14
方法应该是一样的 | d****o
发帖数: 1055 | 25 这个什么时候停？是不是需要记录一个minDistance？
比如
A= 1,2,3
B= 4,5,6
C= 7,8,9
按照这种方法，移到最后是
x=1
y=6
z=8
distance=7
但是最开始没移的时候distance=6
one,
in
【在 z******w 的大作中提到】
: a greedy approach with O(n) time complexity
: 1. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.
: 2. if the distance(x, y) > distance(y, z), move the y to the next number in
: the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
: if distance(x,y) == distance(y,z) move y and z together to the next number.
: 3. update the x,y,z with the new value and repeat the procedure above.
| d****o
发帖数: 1055 | 26 好像这道题的思路是这样的。（不知道和你的方法是不是最后的结果一样。没有怎么看
懂你的方法为什么）
假设
A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
1. 初始化一个全局最小值minDistance=INT_MAX;当前距离curDistance=0;
2. get the first element of a, b and c. let's use x denotes the largest one,
y denotes medium one, z denotes the smallest one.(a=1,b=4,c=5)
3. 找到最小值a，最开始在B[0],那么我就一直把a往右移，直到a>b (13>4),假设移到
了B[i](这里i=1),计算 B[i]之前的一个数B[i-1](就是B[0])和最大值c的差,(c-B[0]=5
-1=4),这个差就是curDistance,如果curDistance小于minDistance,更新minDistance.
4. 更新a,b,c
5. 重复step 2,3,4，直到全部array已经移到了尾部。
one,
in
【在 z******w 的大作中提到】
: a greedy approach with O(n) time complexity
: 1. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.
: 2. if the distance(x, y) > distance(y, z), move the y to the next number in
: the array it belongs to, if distance(x,y) < distance(y,z), move z instead.
: if distance(x,y) == distance(y,z) move y and z together to the next number.
: 3. update the x,y,z with the new value and repeat the procedure above.
| x*******5
发帖数: 152 | 27 The code: 欢迎验证
int Array::Find_value(vector a, vector b, vector c){
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
std::sort(c.begin(),c.end());
int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
int l=INT_MAX;
while(i
l=min(l,max(a[i]-b[j],max(b[j]-c[k],c[k]-a[i])));
if(a[i]<=b[j]&&a[i]<=c[k]) i++;
else if(b[j]<=a[i]&&b[j]<=c[k]) j++;
else if(c[k]<=a[i]&&c[k]<=b[j]) k++;
}
return l;
} | k*****y
发帖数: 744 | 28 考虑六种从小到大排列的可能情况，每种找出最小的distance，再一起比较。
import random
# generate random data
data = [[],[],[]]
for i in range(0,3):
N = random.randint(5, 10)
for j in range(0, N):
data[i].append(random.randrange(0, 1000))
data[i].sort()
#=============================
test_cases = [(0,1,2), (0,2,1),
(1,0,2), (1,2,0),
(2,0,1), (2,1,0)]
pos = [[] for i in range(len(test_cases))]
dist = [1000000]*len(test_cases)
def LowerBound(x, queueID, start):
for i in range( start, len(data[queueID]) ):
if data[queueID][i] >= x:
return i
return len(data[queueID])
# test the case x <= y <= z with
# x in data[id[0]], y in data[id[1]], z in data[id[2]]
for case in range( 0, len(test_cases) ):
id0, id1, id2 = test_cases[case]
pos1, pos2 = 0, 0
for pos0 in range(len(data[id0]) ):
x = data[id0][pos0]
pos1 = LowerBound(x, id1, pos1)
if pos1 < len(data[id1]):
y = data[id1][pos1]
pos2 = LowerBound(y, id2, pos2)
if pos2 < len(data[id2]):
z = data[id2][pos2]
if dist[case] >= z-x:
dist[case] = z-x
pos[case] = [pos0, pos1, pos2]
else:
break
else:
break
min_case = 0
for case in range( 1, len(test_cases) ):
if dist[case] < dist[min_case]:
min_case = case
#=============================
# display data and output
print data[0];
print data[1];
print data[2];
q0, q1, q2 = test_cases[min_case]
pos0, pos1, pos2 = pos[min_case]
print 'the minimal distance is ', dist[min_case]
print 'queue ', q0, ' at ', pos0, ' with value ', data[q0][pos0];
print 'queue ', q1, ' at ', pos1, ' with value ', data[q1][pos1];
print 'queue ', q2, ' at ', pos2, ' with value ', data[q2][pos2];
distance
【在 d****o 的大作中提到】
: You are given with three sorted arrays ( in ascending order), you are
: required to find a triplet ( one element from each array) such that distance
: is minimum.
: Distance is defined like this :
: If a[i], b[j] and c[k] are three elements then
: distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
: Please give a solution in O(n) time complexity
| z****c
发帖数: 602 | 29 可以把三个数组merge到一个大数组中，同时要保留element from where
用三个变量记录most recent element from each array 从大数组的开始遍历，
假设当前数来自数组A，那么找到它到most recent B and most recent C的距离。然后
更新most recent A。
不知这样对不？ | l*****y
发帖数: 56 | 30 像楼主说的，每次把最小的往上移。
用了三个指针，分别指向三个数组，中间会交换指针，min, mid, max，他们分别指向
三个从小到到大排列的数， 距离就是 *max -*min.
最后return the minimal distance, the vector d records the three elements
with minimal distance.
请指正， 谢谢了！
void swap(vector::iterator &a, vector::iterator &b){
vector::iterator temp;
temp=a;
a=b;
b=temp;
}
int min_dist(vector &a, vector &b, vector &c, vector &d){
vector::iterator min=a.begin(), mid=b.begin(), max=c.begin();
int dist=100000; //Make the initial dist large enough.
for(int i=0; i<3; ++i)
{ d.push_back(0);}
while (min!= a.end() && min!= b.end() && min!=c.end()){
if (*min > *mid) swap(min, mid);
if (*mid > *max) swap(mid, max);
if (*min > *mid) swap(min, mid);
int t=*max - *min;
if (dist > t)
{
dist= t;
d[0]=*min;
d[1]=*mid;
d[2]=*max;
}
++min;
}
return dist;
}
【在 c*****e 的大作中提到】
: 每次总是移a,b,c中最小的一个？
| | | H*****1
发帖数: 4815 | 31 1，10， 40
2， 3， 19
5，80， 90
要找三个数的距离之和最小
答案应该是1,3,5
但这种办法不可能找到啊
one,
【在 d****o 的大作中提到】
: 好像这道题的思路是这样的。（不知道和你的方法是不是最后的结果一样。没有怎么看
: 懂你的方法为什么）
: 假设
: A = {4, 10, 15, 20}
: B = {1, 13, 29}
: C = {5, 14, 28}
: 1. 初始化一个全局最小值minDistance=INT_MAX;当前距离curDistance=0;
: 2. get the first element of a, b and c. let's use x denotes the largest one,
: y denotes medium one, z denotes the smallest one.(a=1,b=4,c=5)
: 3. 找到最小值a，最开始在B[0],那么我就一直把a往右移，直到a>b (13>4),假设移到
| b***u
发帖数: 12010 | 32 不是找距离和最小，而是max。 125和135是一样的
【在 H*****1 的大作中提到】
: 1，10， 40
: 2， 3， 19
: 5，80， 90
: 要找三个数的距离之和最小
: 答案应该是1,3,5
: 但这种办法不可能找到啊
:
: one,
| b***u
发帖数: 12010 | 33 最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。 | b******v
发帖数: 1493 | 34 1, 2, 5也可以吧
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 H*****1 的大作中提到】
: 1，10， 40
: 2， 3， 19
: 5，80， 90
: 要找三个数的距离之和最小
: 答案应该是1,3,5
: 但这种办法不可能找到啊
:
: one,
| z*****n
发帖数: 447 | 35 每次把（X,Y，Z）中最小的往上移一位，计算一个min distance，得到一个新的（X，Y
，Z），重复以上步骤，最多一共 3N 次可以完成，O(N) | h*****y
发帖数: 218 | 36 这个应该好证明吧？
【在 b***u 的大作中提到】
: 最讨厌greedy问题了。方法简单但是证明麻烦，难想到。dp比greedy容易多了。
| h*****y
发帖数: 218 | 37 每次移动最大的，只会让结果更大
移动中间的，最大的不会变
但是，不知道是否一定是全局最优解
大家能够给个证明么？
【在 h*****y 的大作中提到】
: 这个应该好证明吧？
| i***h
发帖数: 12655 | 38 这个不就是我前两天说的题么?
改头换面又出来了, 果然经典啊. | p*u
发帖数: 136 | 39 nice code!
【在 x*******5 的大作中提到】
: The code: 欢迎验证
: int Array::Find_value(vector a, vector b, vector c){
: std::sort(a.begin(),a.end());
: std::sort(b.begin(),b.end());
: std::sort(c.begin(),c.end());
: int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
: int l=INT_MAX;
: while(i: l=min(l,max(a[i]-b[j],max(b[j]-c[k],c[k]-a[i])));
: if(a[i]<=b[j]&&a[i]<=c[k]) i++;
| x*******5
发帖数: 152 | 40 证明也许比较难，但是我是这样做的：
/*Description: given three arrays A, B,C, find three indices i,j, k such that
the value l=max((a-b),(b-c), (c-a)) is minimized
Input: vector a, vector b, vector c
Output: void
K.O.: sorting, merge sort variant
*/
int Array::Find_value_brute(vector a, vector b, vector c){
int n=a.size(),m=b.size(),p=c.size(),l=INT_MAX;
for(int i=0;i
for(int j=0;j
for(int k=0;k
int ta=abs(a[i]-b[j]),tb=abs(b[j]-c[k]),tc=abs(c[k]-a[i]);
l=min(l,max(ta,max(tb,tc)));
}
return l;
}
int Array::Find_value(vector a, vector b, vector c){
std::sort(a.begin(),a.end());
std::sort(b.begin(),b.end());
std::sort(c.begin(),c.end());
int i=0,j=0,k=0,n=a.size(),m=b.size(),p=c.size();
int l=INT_MAX;
while(i
int ta=abs(a[i]-b[j]),tb=abs(b[j]-c[k]),tc=abs(c[k]-a[i]);
l=min(l,max(ta,max(tb,tc)));
if(a[i]<=b[j]&&a[i]<=c[k]) i++;
else if(b[j]<=a[i]&&b[j]<=c[k]) j++;
else if(c[k]<=a[i]&&c[k]<=b[j]) k++;
}
return l;
}
提出的方法应该和brute force的结果一样，于是
int count=0;
for(int i=0;i<20000;i++){
vector a=Pearl::generate_int_swap(10,100);
vector b=Pearl::generate_int_knuth(10,200);
vector c=Pearl::generate_int_floyd(10,300);
int t1=Array::Find_value_brute(a,b,c);
int t2=Array::Find_value(a,b,c);
if (t1!=t2)
count++;
}
cout<
a,b,c是三个长度为10的随即数组，三个函数是我自己写的随即数生成器（idea来自编
程珠玑，所以namespace取的是Pearl）
多次实验，count都是0 | | | w***y
发帖数: 6251 | 41 翻出这倒老题, 看了大家的回复, 都是讲算法没有讲证明的
我理解算法是:
3个数, 找出max/median/min, 这三个数的 distance = max-min
如果要最小化distance, 就把min变大直到min超过median了, 就重新计算distance, 并
更新max/median/min --- 直到min移到结束了
我愚钝, 不会自己证明啊 555555555 这种greedy的方法减少了很多不必要的搜索,
但是怎么证明这个是对的? //汗 | l*y
发帖数: 21010 | 42 按三路归并的办法，把三个数组并成一个，在这个过程中就找到了所需triplet。
首先设minDistance为MAXINT。归并的过程中，每次选三个数组各自最小元素的最小的
拿出来放入归并好的序列。假设某时刻三个数组的最小元素分别为ai,bj,ck，且ai最小
，我们记录max(|ai-bj|,|ai-ck|)的值。这个值就是在最后归并好的序列中，以ai为最
小数的triplet的Distance（可用反证法证明，因为bj和ck分别是另外两个数组中比ai
大的最小的数，所以再取更大的数Distance一定更大），记为curDistance，然后更新
minDistance如果比它更小（并且记住该minDistance对应的triplet是ai,bj,ck）。
完成归并后，我们就得到了minDistance和所需的那个triplet。
distance
【在 d****o 的大作中提到】
: You are given with three sorted arrays ( in ascending order), you are
: required to find a triplet ( one element from each array) such that distance
: is minimum.
: Distance is defined like this :
: If a[i], b[j] and c[k] are three elements then
: distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
: Please give a solution in O(n) time complexity
| f*********i
发帖数: 197 | 43 What about the duplicate cases?
{2, 9, 15}
{5, 9, 13}
{7, 19, 21}
After reaching 9,9,7, which "9" entry should be increased? | h**********y
发帖数: 1293 | | g**x
发帖数: 373 | 45 Suppose three arrays got merged into one in ascending order, the triplet
with minimum distance must appear as ... Xi, Yj, Zk ... OR ... Xi, Yj, Yj+1,
..., Yj',Zk ... The distance is Zk - Xi.
So one scan/merge on three arrays by ascending order, can detect the triplet
in above patterns and find out the minimum distance for sure.
【在 w***y 的大作中提到】
: 翻出这倒老题, 看了大家的回复, 都是讲算法没有讲证明的
: 我理解算法是:
: 3个数, 找出max/median/min, 这三个数的 distance = max-min
: 如果要最小化distance, 就把min变大直到min超过median了, 就重新计算distance, 并
: 更新max/median/min --- 直到min移到结束了
:
: 我愚钝, 不会自己证明啊 555555555 这种greedy的方法减少了很多不必要的搜索,
: 但是怎么证明这个是对的? //汗
| t*****j
发帖数: 1105 | 46 三路归并，然后sliding window，扫描至结束。
ai
【在 l*y 的大作中提到】
: 按三路归并的办法，把三个数组并成一个，在这个过程中就找到了所需triplet。
: 首先设minDistance为MAXINT。归并的过程中，每次选三个数组各自最小元素的最小的
: 拿出来放入归并好的序列。假设某时刻三个数组的最小元素分别为ai,bj,ck，且ai最小
: ，我们记录max(|ai-bj|,|ai-ck|)的值。这个值就是在最后归并好的序列中，以ai为最
: 小数的triplet的Distance（可用反证法证明，因为bj和ck分别是另外两个数组中比ai
: 大的最小的数，所以再取更大的数Distance一定更大），记为curDistance，然后更新
: minDistance如果比它更小（并且记住该minDistance对应的triplet是ai,bj,ck）。
: 完成归并后，我们就得到了minDistance和所需的那个triplet。
:
: distance
| c****m
发帖数: 11 | 47 这样不行吧，sliding window是固定size=3么？
【在 t*****j 的大作中提到】
: 三路归并，然后sliding window，扫描至结束。
:
: ai
|
|
