L****Y
发帖数: 355 | 1 From the set of natural integer numbers
Let x = 1234 = {1, 2, 3, 4}
Let y = 2410 = {2, 4, 1, 0}
Write an algorithm to compute the rearrangement of x that is closest to y
but still greater than y. Both x and y have the same number of digits.
So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is
greater than y = 2410 and closer than any other arrangements of x.
And whats the time complexity of this algorithm?
Any efficient algorithm？ | c********t
发帖数: 5706 | 2 x是sorted吗？ 不是的话，可以sort, 然后binary search each digit in y
is
【在 L****Y 的大作中提到】
: From the set of natural integer numbers
: Let x = 1234 = {1, 2, 3, 4}
: Let y = 2410 = {2, 4, 1, 0}
: Write an algorithm to compute the rearrangement of x that is closest to y
: but still greater than y. Both x and y have the same number of digits.
: So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is
: greater than y = 2410 and closer than any other arrangements of x.
: And whats the time complexity of this algorithm?
: Any efficient algorithm？
| p*****2
发帖数: 21240 | | L****Y
发帖数: 355 | 4 不是sort的。 可以展开说说？
【在 c********t 的大作中提到】
: x是sorted吗？ 不是的话，可以sort, 然后binary search each digit in y
:
: is
| L****Y
发帖数: 355 | 5 怎么个做法？ Treeset是java里面的？
【在 p*****2 的大作中提到】
: Treeset nlogn
| d**********x
发帖数: 4083 | 6 这里的integer有范围吗？
例子里面都是0-9,但是看题目好像没有限制？
is
【在 L****Y 的大作中提到】
: From the set of natural integer numbers
: Let x = 1234 = {1, 2, 3, 4}
: Let y = 2410 = {2, 4, 1, 0}
: Write an algorithm to compute the rearrangement of x that is closest to y
: but still greater than y. Both x and y have the same number of digits.
: So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is
: greater than y = 2410 and closer than any other arrangements of x.
: And whats the time complexity of this algorithm?
: Any efficient algorithm？
| L****Y
发帖数: 355 | 7 就是0-9
【在 d**********x 的大作中提到】
: 这里的integer有范围吗？
: 例子里面都是0-9,但是看题目好像没有限制？
:
: is
| d**********x
发帖数: 4083 | 8 先counting，把0-9的所有数字数一遍有多少
然后和第二个匹配，one by one
这样有两种情况，
1) 完全匹配，变成寻找next lexical order permutation，不提了
2) 到某个地方，set 1里面的数字不够了，这也有两种情况
i. set 1里面存在比当前set 2里面的数字大的，那么把最小的那个比set 2里面大的
添上，然后后面从小到大填
ii. set 1里面只剩下比当前set 2里面数字小的，这时候要从当前点往回走，把填进
去的数字再退回来，找到第一个位置，使得set 1里面的剩余数字中存在比set 2中的当
前数字大的，填进去，然后后面从小到大填。
如果最后发现set 1里面的数字无法比set 2大，输出异常。
is
【在 L****Y 的大作中提到】
: From the set of natural integer numbers
: Let x = 1234 = {1, 2, 3, 4}
: Let y = 2410 = {2, 4, 1, 0}
: Write an algorithm to compute the rearrangement of x that is closest to y
: but still greater than y. Both x and y have the same number of digits.
: So in the example above, the answer would be { 2, 4, 1, 3 } = 2413 which is
: greater than y = 2410 and closer than any other arrangements of x.
: And whats the time complexity of this algorithm?
: Any efficient algorithm？
| p*****2
发帖数: 21240 | 9
嗯。就是这个思路。如果只是0-9， O(n)就可以了。
【在 d**********x 的大作中提到】
: 先counting，把0-9的所有数字数一遍有多少
: 然后和第二个匹配，one by one
: 这样有两种情况，
: 1) 完全匹配，变成寻找next lexical order permutation，不提了
: 2) 到某个地方，set 1里面的数字不够了，这也有两种情况
: i. set 1里面存在比当前set 2里面的数字大的，那么把最小的那个比set 2里面大的
: 添上，然后后面从小到大填
: ii. set 1里面只剩下比当前set 2里面数字小的，这时候要从当前点往回走，把填进
: 去的数字再退回来，找到第一个位置，使得set 1里面的剩余数字中存在比set 2中的当
: 前数字大的，填进去，然后后面从小到大填。
| L****Y
发帖数: 355 | 10 很赞。
【在 d**********x 的大作中提到】
: 先counting，把0-9的所有数字数一遍有多少
: 然后和第二个匹配，one by one
: 这样有两种情况，
: 1) 完全匹配，变成寻找next lexical order permutation，不提了
: 2) 到某个地方，set 1里面的数字不够了，这也有两种情况
: i. set 1里面存在比当前set 2里面的数字大的，那么把最小的那个比set 2里面大的
: 添上，然后后面从小到大填
: ii. set 1里面只剩下比当前set 2里面数字小的，这时候要从当前点往回走，把填进
: 去的数字再退回来，找到第一个位置，使得set 1里面的剩余数字中存在比set 2中的当
: 前数字大的，填进去，然后后面从小到大填。
| Y********f
发帖数: 410 | 11 思路很好啊。
可以把1)和2)ii合并
1.如果匹配完或者剩下的都比当前字符小，把剩下的字符的最大排列放到剩下的位置。
再用next permutation
【在 d**********x 的大作中提到】
: 先counting，把0-9的所有数字数一遍有多少
: 然后和第二个匹配，one by one
: 这样有两种情况，
: 1) 完全匹配，变成寻找next lexical order permutation，不提了
: 2) 到某个地方，set 1里面的数字不够了，这也有两种情况
: i. set 1里面存在比当前set 2里面的数字大的，那么把最小的那个比set 2里面大的
: 添上，然后后面从小到大填
: ii. set 1里面只剩下比当前set 2里面数字小的，这时候要从当前点往回走，把填进
: 去的数字再退回来，找到第一个位置，使得set 1里面的剩余数字中存在比set 2中的当
: 前数字大的，填进去，然后后面从小到大填。
|
|
