x*****0
发帖数: 452 | 1 There is a straight road with 'n' number of milestones. You are given an
array with the distance between all the pairs of milestones in some random
order. Find the position of milestones.
Example:
Consider a road with 4 milestones (a,b,c,d) : a---3Km---b---5Km---c---2Km---
d
Distance between a and b is 3
Distance between a and c is 8
Distance between a and d is 10
Distance between b and c is 5
Distance between b and d is 7
Distance between c and d is 2
All the above values are given in a random order say 7, 10, 5, 2, 8, 3.
The output must be 3, 5, 2 or 2, 5, 3.
简而言之，这道题的意思就是：
给定一个数组长度为n的数组，n的限制就是必然存在一个整数x，使得 n=(x-1)+(x-2)+
...+1。从这个数组中找出x个元素，假设为A1, A2, ..., Ax，使得 A2+A1, A3+A2, A3
+A2+A1, ..., Ax+A（x-1）, ..., Ax+A（x-1）+...+A1 都出现在原始的数组中。
我的解法：
暴力穷举。
（1）计算出x
（2）一共有P(n,x)中可能得排列。
（3) 验证每种排列是否可行。
大家觉得呢？是不是应该有更好的解法。 | s*******s
发帖数: 1031 | 2 暴力算法是 n! 时间复杂度。
我想出的是DFS一个二叉树， O(2^n)的复杂度。
将这个distance 序列按照降序排序。O(n log n)
进入递归程序:
1. suppose d1, d2, d3,...dn是降序排列的数。
d1最大，所以d1肯定是两个端点的距离。 现在要确定下一个点。
d2或者d3将会是去掉最后端点(或者最前端点)的剩余的长度。
2. 对d2,如果能在d3, d4,..., dn中找到一个di，使得 di = d1 - d2，那么d2有可能是
一个合格的子问题，在原来的序列中去掉d1, di，递归调用。如果找不到这么一个di,那
么d2不是valid choice
3. 对d3，如果能在d2, d4, ..., dn中找到dj，使得dj = d1 - d3，那么，类似于2，
对d3进行递归调用。
如果d2, d3都无法找到相应的di, dj，那么这个序列是非法的序列，返回。
stop condition:
当序列是空的时侯我们找到了一格valid结果。
Time: O(2^n） 因为是对二叉树进行DFS。
求更好的解法！
【在 x*****0 的大作中提到】
: There is a straight road with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones (a,b,c,d) : a---3Km---b---5Km---c---2Km---
: d
: Distance between a and b is 3
: Distance between a and c is 8
: Distance between a and d is 10
: Distance between b and c is 5
| s*******s
发帖数: 1031 | 3 最小元素不一定在一头一尾的。
比如：
a...............b..c..d..............e
最小的两个元素在中间。
晕，我的算法也有问题。
看来对剩下的元素做2Sum，找出的每一对都可能是valid选择。那就是多叉树了。 | s*******s
发帖数: 1031 | | r**h
发帖数: 1288 | 5 找出最左最后两个元素之后，如何删除和这两个元素相关的所有值呢？
有可能包含了被排除了的元素的和还在下一次要做two sum的子集里面吗？ | c*********m
发帖数: 43 | 6 ac 不一定比de小吧？你没法确定这两个的关系啊。 | r*******e
发帖数: 7583 | 7 有道理，我那个思路是错的
【在 c*********m 的大作中提到】
: ac 不一定比de小吧？你没法确定这两个的关系啊。
| c******a
发帖数: 789 | 8 设全长为C_all，最左最右区间为Cl, Cr
array一定会有C_all, Cr, Cl, C_all-Cr, C_all-Cl。这样能不能暴力出最左最右，然
后开始递归？ | d*****n
发帖数: 49 | 9 there is a simply solution to this problem. Let's call the
distances between any two milestones "Atoms", and all the
others "Composites". The target is to output all the Atoms.
This algorithm is based on the fact that the Atoms are
among the smallest numbers in the array, and the largest
number is the sum of all Atoms. So starting with the
beginning of the sorted array can optimize the total
iterations a lot.
1. sort the array by increasing order.
2. find the number of all Atoms, say N (easy to find with
the composition Cn2 formula n(n-1)/2).
3. note that first 2 of the sorted array are gurrantteed to
be Atoms. For the first N numbers, see if any of them is
equal to sum of any numbers before it, if none of them is,
then these N numbers are already Atoms. Return.
4. Otherwise (if any of the N numbers is a sum of some
numbers before it, call this number X), then continue to
look at its adjacent number. If the adjacent number is NOT
a duplicate (!= X), then X is NOT an atom (simple to
prove), X can be excluded and continue to include N+1
number into this sub-array.
5. in the last step in 4, if the adjacent number IS a
duplicate of X, then test if it is the sum of a different
set of numbers before it (different set from X). E.g., if
the first 4 are 1, 2, 3, 3, X is the first 3 (=1+2), then
find that there is no other numbers (other than the first
2) that can sum to be 3, then this test is false. If this
test is false, that means 3 is an Atom. If this test is
true, then continue the test in step 4 for this number.
Continue with steps 4 and 5, you should find all N atoms in
the end. To verify, they should sum up to be equal to the
largest number (last in the sorted array). (This condition
can also be used to quickly exclude impossible scenarios in
steps 4-5.)
Complexity? Not sure, but seems if the last condition is leveraged some
extreme situations can be accelerated a lot (e.g., 1,2,3,100 --> 1,2,3,3,5,6
,100,103,106, the 7th number (100) can be quickly found due to sum must be
106)
【在 x*****0 的大作中提到】
: There is a straight road with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones (a,b,c,d) : a---3Km---b---5Km---c---2Km---
: d
: Distance between a and b is 3
: Distance between a and c is 8
: Distance between a and d is 10
: Distance between b and c is 5
| r*******e
发帖数: 7583 | 10 好像不止是找出atoms，还得把atoms的排列顺序找出来
,6
random
2Km-
【在 d*****n 的大作中提到】
: there is a simply solution to this problem. Let's call the
: distances between any two milestones "Atoms", and all the
: others "Composites". The target is to output all the Atoms.
: This algorithm is based on the fact that the Atoms are
: among the smallest numbers in the array, and the largest
: number is the sum of all Atoms. So starting with the
: beginning of the sorted array can optimize the total
: iterations a lot.
: 1. sort the array by increasing order.
: 2. find the number of all Atoms, say N (easy to find with
| | | d*****n
发帖数: 49 | 11 If positions are also required, there needs just a little more effort after
finding all the Atoms. Some tricks I can see: suppose array length is M,
after sorting:
difference of Mth and M-1th number gives you the first Atom.
(these can be leveraged to further accelerate finding the Atoms as well).
【在 r*******e 的大作中提到】
: 好像不止是找出atoms，还得把atoms的排列顺序找出来
:
: ,6
: random
: 2Km-
| g*******n
发帖数: 214 | 12 想到一个算法，O(n^2)不知道行不行：
一个大循环，里面的invariant就是最小的distance就是单个的distance。把这个
distance从数组中删掉，再找到这个distance应该在结果数组中的位置。每次都取最小
值直到这个数组中只剩下一个值。具体来说就是
1.先把distance数组排序，可以得知最小的一个肯定是单个的distance，叫做min。把
这个min从数组中删掉。
2.遍历剩下的值，如果有任意两个值满足min+distanceA=distanceB的话，说明min就说
明distanceB包含了min。那么就删去distanceB。这步做完之后，所有包含min的都被删
掉了。
3.记录第2部被删掉的个数，包括min本身，一共是n个。那么计算C(x,1)+C(length-x,1
)==n中x的值，min就应该在结果数组中从一边开始数，第x-1个没有被赋过值的位置。
4.把剩下的数组作为新的数组，返回到第1步重复。
这样就可以每次得到一个值。具体的实现的话不用用数组，可以用heap来得到最小值。
还有一些细节问题，比如有duplicate： 5+5 和 8+2 或者 1+3+6 的时候，有必要记录
10有几个，每次只能删一个等等。 | g*******n
发帖数: 214 | 13 可能有点confusing。第3步中，被删的个数是m个吧(避免和n混淆)。C(x,1)+C(length-
x,1)==m是这样来的：
比如有a个distance，那么就应该有a+1个顶点。包括min的所有distance的个数应该是
从min左边任意取一个顶点加上从min后边任意取一个顶点，其中length就是指a+1。这
样一来就可以和第2步被删掉的个数比较，从而找到x的值。min就应该是在结果数组中
的从一边开始没有被赋值过的第x-1个数。 | x*****0
发帖数: 452 | 14 There is a straight road with 'n' number of milestones. You are given an
array with the distance between all the pairs of milestones in some random
order. Find the position of milestones.
Example:
Consider a road with 4 milestones (a,b,c,d) : a---3Km---b---5Km---c---2Km---
d
Distance between a and b is 3
Distance between a and c is 8
Distance between a and d is 10
Distance between b and c is 5
Distance between b and d is 7
Distance between c and d is 2
All the above values are given in a random order say 7, 10, 5, 2, 8, 3.
The output must be 3, 5, 2 or 2, 5, 3.
简而言之，这道题的意思就是：
给定一个数组长度为n的数组，n的限制就是必然存在一个整数x，使得 n=(x-1)+(x-2)+
...+1。从这个数组中找出x个元素，假设为A1, A2, ..., Ax，使得 A2+A1, A3+A2, A3
+A2+A1, ..., Ax+A（x-1）, ..., Ax+A（x-1）+...+A1 都出现在原始的数组中。
我的解法：
暴力穷举。
（1）计算出x
（2）一共有P(n,x)中可能得排列。
（3) 验证每种排列是否可行。
大家觉得呢？是不是应该有更好的解法。 | s*******s
发帖数: 1031 | 15 暴力算法是 n! 时间复杂度。
我想出的是DFS一个二叉树， O(2^n)的复杂度。
将这个distance 序列按照降序排序。O(n log n)
进入递归程序:
1. suppose d1, d2, d3,...dn是降序排列的数。
d1最大，所以d1肯定是两个端点的距离。 现在要确定下一个点。
d2或者d3将会是去掉最后端点(或者最前端点)的剩余的长度。
2. 对d2,如果能在d3, d4,..., dn中找到一个di，使得 di = d1 - d2，那么d2有可能是
一个合格的子问题，在原来的序列中去掉d1, di，递归调用。如果找不到这么一个di,那
么d2不是valid choice
3. 对d3，如果能在d2, d4, ..., dn中找到dj，使得dj = d1 - d3，那么，类似于2，
对d3进行递归调用。
如果d2, d3都无法找到相应的di, dj，那么这个序列是非法的序列，返回。
stop condition:
当序列是空的时侯我们找到了一格valid结果。
Time: O(2^n） 因为是对二叉树进行DFS。
求更好的解法！
【在 x*****0 的大作中提到】
: There is a straight road with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones (a,b,c,d) : a---3Km---b---5Km---c---2Km---
: d
: Distance between a and b is 3
: Distance between a and c is 8
: Distance between a and d is 10
: Distance between b and c is 5
| s*******s
发帖数: 1031 | 16 最小元素不一定在一头一尾的。
比如：
a...............b..c..d..............e
最小的两个元素在中间。
晕，我的算法也有问题。
看来对剩下的元素做2Sum，找出的每一对都可能是valid选择。那就是多叉树了。
【在 r*******e 的大作中提到】
: 好像不止是找出atoms，还得把atoms的排列顺序找出来
:
: ,6
: random
: 2Km-
| s*******s
发帖数: 1031 | 17 多谢！你说得对。
终于明白你的意思了。
【在 r*******e 的大作中提到】
: 好像不止是找出atoms，还得把atoms的排列顺序找出来
:
: ,6
: random
: 2Km-
| r**h
发帖数: 1288 | 18 找出最左最后两个元素之后，如何删除和这两个元素相关的所有值呢？
有可能包含了被排除了的元素的和还在下一次要做two sum的子集里面吗？
【在 r*******e 的大作中提到】
: 好像不止是找出atoms，还得把atoms的排列顺序找出来
:
: ,6
: random
: 2Km-
| c*********m
发帖数: 43 | 19 ac 不一定比de小吧？你没法确定这两个的关系啊。
【在 r*******e 的大作中提到】
: 好像不止是找出atoms，还得把atoms的排列顺序找出来
:
: ,6
: random
: 2Km-
| r*******e
发帖数: 7583 | 20 有道理，我那个思路是错的
【在 c*********m 的大作中提到】
: ac 不一定比de小吧？你没法确定这两个的关系啊。
| | | c******a
发帖数: 789 | 21 设全长为C_all，最左最右区间为Cl, Cr
array一定会有C_all, Cr, Cl, C_all-Cr, C_all-Cl。这样能不能暴力出最左最右，然
后开始递归？ | d*****n
发帖数: 49 | 22 there is a simply solution to this problem. Let's call the
distances between any two milestones "Atoms", and all the
others "Composites". The target is to output all the Atoms.
This algorithm is based on the fact that the Atoms are
among the smallest numbers in the array, and the largest
number is the sum of all Atoms. So starting with the
beginning of the sorted array can optimize the total
iterations a lot.
1. sort the array by increasing order.
2. find the number of all Atoms, say N (easy to find with
the composition Cn2 formula n(n-1)/2).
3. note that first 2 of the sorted array are gurrantteed to
be Atoms. For the first N numbers, see if any of them is
equal to sum of any numbers before it, if none of them is,
then these N numbers are already Atoms. Return.
4. Otherwise (if any of the N numbers is a sum of some
numbers before it, call this number X), then continue to
look at its adjacent number. If the adjacent number is NOT
a duplicate (!= X), then X is NOT an atom (simple to
prove), X can be excluded and continue to include N+1
number into this sub-array.
5. in the last step in 4, if the adjacent number IS a
duplicate of X, then test if it is the sum of a different
set of numbers before it (different set from X). E.g., if
the first 4 are 1, 2, 3, 3, X is the first 3 (=1+2), then
find that there is no other numbers (other than the first
2) that can sum to be 3, then this test is false. If this
test is false, that means 3 is an Atom. If this test is
true, then continue the test in step 4 for this number.
Continue with steps 4 and 5, you should find all N atoms in
the end. To verify, they should sum up to be equal to the
largest number (last in the sorted array). (This condition
can also be used to quickly exclude impossible scenarios in
steps 4-5.)
Complexity? Not sure, but seems if the last condition is leveraged some
extreme situations can be accelerated a lot (e.g., 1,2,3,100 --> 1,2,3,3,5,6
,100,103,106, the 7th number (100) can be quickly found due to sum must be
106)
【在 x*****0 的大作中提到】
: There is a straight road with 'n' number of milestones. You are given an
: array with the distance between all the pairs of milestones in some random
: order. Find the position of milestones.
: Example:
: Consider a road with 4 milestones (a,b,c,d) : a---3Km---b---5Km---c---2Km---
: d
: Distance between a and b is 3
: Distance between a and c is 8
: Distance between a and d is 10
: Distance between b and c is 5
| r*******e
发帖数: 7583 | 23 好像不止是找出atoms，还得把atoms的排列顺序找出来
,6
random
2Km-
【在 d*****n 的大作中提到】
: there is a simply solution to this problem. Let's call the
: distances between any two milestones "Atoms", and all the
: others "Composites". The target is to output all the Atoms.
: This algorithm is based on the fact that the Atoms are
: among the smallest numbers in the array, and the largest
: number is the sum of all Atoms. So starting with the
: beginning of the sorted array can optimize the total
: iterations a lot.
: 1. sort the array by increasing order.
: 2. find the number of all Atoms, say N (easy to find with
| d*****n
发帖数: 49 | 24 If positions are also required, there needs just a little more effort after
finding all the Atoms. Some tricks I can see: suppose array length is M,
after sorting:
difference of Mth and M-1th number gives you the first Atom.
(these can be leveraged to further accelerate finding the Atoms as well).
【在 r*******e 的大作中提到】
: 好像不止是找出atoms，还得把atoms的排列顺序找出来
:
: ,6
: random
: 2Km-
| g*******n
发帖数: 214 | 25 想到一个算法，O(n^2)不知道行不行：
一个大循环，里面的invariant就是最小的distance就是单个的distance。把这个
distance从数组中删掉，再找到这个distance应该在结果数组中的位置。每次都取最小
值直到这个数组中只剩下一个值。具体来说就是
1.先把distance数组排序，可以得知最小的一个肯定是单个的distance，叫做min。把
这个min从数组中删掉。
2.遍历剩下的值，如果有任意两个值满足min+distanceA=distanceB的话，说明min就说
明distanceB包含了min。那么就删去distanceB。这步做完之后，所有包含min的都被删
掉了。
3.记录第2部被删掉的个数，包括min本身，一共是n个。那么计算C(x,1)+C(length-x,1
)==n中x的值，min就应该在结果数组中从一边开始数，第x-1个没有被赋过值的位置。
4.把剩下的数组作为新的数组，返回到第1步重复。
这样就可以每次得到一个值。具体的实现的话不用用数组，可以用heap来得到最小值。
还有一些细节问题，比如有duplicate： 5+5 和 8+2 或者 1+3+6 的时候，有必要记录
10有几个，每次只能删一个等等。 | g*******n
发帖数: 214 | 26 可能有点confusing。第3步中，被删的个数是m个吧(避免和n混淆)。C(x,1)+C(length-
x,1)==m是这样来的：
比如有a个distance，那么就应该有a+1个顶点。包括min的所有distance的个数应该是
从min左边任意取一个顶点加上从min后边任意取一个顶点，其中length就是指a+1。这
样一来就可以和第2步被删掉的个数比较，从而找到x的值。min就应该是在结果数组中
的从一边开始没有被赋值过的第x-1个数。 | z***k
发帖数: 282 | 27 数学专业，在做面试题。有一个想法，某些地方跟上面某位大牛的类似。欢迎探讨。
一共n个点，C^n_2个数
1，找到最大的数，就是总长度，记为x(n)
2，按从小到大排列，a1,a2,...从a1开始，找到与之相加=x(n)的配对,记为（a1,b1)，
（a2,b2)...最多只取不同的六对，算上重复的，可能超过6对。
3, 两个最小ai，就是两头的两段。记任何一个为c1，另一个为cn-1。删除这两对，留
下4对（可能少于4对）不重复的（ai,bi)。从C^n_2这些数里面，减去a1,b1,a2,b2这四
个数，不要删重复的。为了减少下面的循环计算量。
4, 总长度x(n)减去c1,cn-1,就是去掉两头的剩下的总长度
5，用剩下的总长度，重复2,3,4
6，从第二次循环开始，加入一个判断。先得到c2,cn-2,然后判断哪个是c2，哪个是cn-
2。方法：（先解释下为啥上个循环要六对，为了这个循环里面，要判断c1,c2,cn-2,cn
-1的两两组合，一共是六个不同可能）。
首先从第三步剩下的配对的ai里，尝试找到c1+c2,c1+(cn-2), c2+(cn-1),(cn-1)+(cn-
2)。如果这4个数中只有2个出现，那就可以确定c2，cn-2.如果不止两个，就做下面的
检验：
首先，如果c1=cn-1,这次得到的两个数，任何一个都可以设为c2,进入下个循环，
如果c2=cn-2，没问题继续下个循环。
如果c2,cn-2中有一个等于上个循环的cn-1，那令cn-2=cn-1。
这个检验应该包含所有的情况吧，没有仔细证明。
不懂啥是时间复杂度，这个方法的时间复杂度多少？ | D**********d
发帖数: 849 | 28 其实就是上三角排序问题:
将 n(n-1)/2 个 distances 从大到小排序
第一个一定在左上角，记为 a(1,n)
2-3 一定是从左上起第二对角线上的 a(1,n-1), a(2,n)
4-6 一定是从左上起第三对角线上的 a(1,n-2), a(2,n-1), a(3,n)
...
n(n-1)/2-n+2 --- n(n-1)/2 一定是上次对角线上的
如何确定每条对角线上的次序?
1. 利用上一对角线元素与本对角线元素的差，看有没有元素在次对角线上与之对应.
2. 因为正反对称性， a(1,n-1), a(2,n) 如何排都是可行解 | z***k
发帖数: 282 | 29 这个上三角的想法很好。不过有些细节没看懂。
是不是基于：左上角为最上层的话，每一层的数，都会大于其下面一层的？如果这样，
下面的情况就不对。从左上角起：
12
11 4
10 3 3
9 2 2 2
8 1 1 1 1
【在 D**********d 的大作中提到】
: 其实就是上三角排序问题:
: 将 n(n-1)/2 个 distances 从大到小排序
: 第一个一定在左上角，记为 a(1,n)
: 2-3 一定是从左上起第二对角线上的 a(1,n-1), a(2,n)
: 4-6 一定是从左上起第三对角线上的 a(1,n-2), a(2,n-1), a(3,n)
: ...
: n(n-1)/2-n+2 --- n(n-1)/2 一定是上次对角线上的
: 如何确定每条对角线上的次序?
: 1. 利用上一对角线元素与本对角线元素的差，看有没有元素在次对角线上与之对应.
: 2. 因为正反对称性， a(1,n-1), a(2,n) 如何排都是可行解
| r**********o
发帖数: 50 | 30 题目是给出所有milestone pair的distance了么？ 还是只给部分的？
如果是给出所有的，那么排序找出最大值，之后做2Sum，2Sum的合格对，排序，算出结
果，为什么不行呢？ | | | z***k
发帖数: 282 | 31 如果最底层有大量的1和2，那么每次都会有很多2sum对，这样没法确定顺序吧
比如如果答案是112121212一共13,就有所有配对，而且有重复的。
【在 r**********o 的大作中提到】
: 题目是给出所有milestone pair的distance了么？ 还是只给部分的？
: 如果是给出所有的，那么排序找出最大值，之后做2Sum，2Sum的合格对，排序，算出结
: 果，为什么不行呢？
| b*******e
发帖数: 123 | 32 这样行不行。
最大距离的两个端点设为[a,b]
然后对所有距离[a x_i]排序，[a,x_0,....,x_n, b]就是结果。
复杂度
o(n(n-1)/2) + o(n*log(n)) |
|
