k****t
发帖数: 184 | 1 Given an unsorted array of positive integers, is it possible to find a pair
of integers from that array that sum up to a given sum?
Constraints: This should be done in O(n) and in-place (without any external
storage like arrays, hash-maps) (you can use extra variables/pointers)
If this is not possible, can there be a proof given for the same?
感觉不存在这样的解法。但怎么证明？ |
r*g
发帖数: 186 | 2 best result I get:
http://www.ic.unicamp.br/~rezende/ensino/mo619/Chan,RefinedUppe
pair
external
【在 k****t 的大作中提到】
: Given an unsorted array of positive integers, is it possible to find a pair
: of integers from that array that sum up to a given sum?
: Constraints: This should be done in O(n) and in-place (without any external
: storage like arrays, hash-maps) (you can use extra variables/pointers)
: If this is not possible, can there be a proof given for the same?
: 感觉不存在这样的解法。但怎么证明？
|
l*****8
发帖数: 1083 | 3 不存在，因为在one pass的过程中丢失了前面的所有信息，所以对于数组中的任意一个
数字都不能确定前面是否有能配对的数字。
pair
external
【在 k****t 的大作中提到】
: Given an unsorted array of positive integers, is it possible to find a pair
: of integers from that array that sum up to a given sum?
: Constraints: This should be done in O(n) and in-place (without any external
: storage like arrays, hash-maps) (you can use extra variables/pointers)
: If this is not possible, can there be a proof given for the same?
: 感觉不存在这样的解法。但怎么证明？
|
d********t
发帖数: 9628 | 4 RE
【在 l*****8 的大作中提到】
: 不存在，因为在one pass的过程中丢失了前面的所有信息，所以对于数组中的任意一个
: 数字都不能确定前面是否有能配对的数字。
:
: pair
: external
|
r*g
发帖数: 186 | 5 intuitively true, could you plz give a more rigorous proof?
【在 l*****8 的大作中提到】
: 不存在，因为在one pass的过程中丢失了前面的所有信息，所以对于数组中的任意一个
: 数字都不能确定前面是否有能配对的数字。
:
: pair
: external
|
l*****8
发帖数: 1083 | 6 I think it's clear enough and logically true. The point here is that you
cannot keep any previous information. Any previous numbers become unknown.
【在 r*g 的大作中提到】
: intuitively true, could you plz give a more rigorous proof?
|
r*g
发帖数: 186 | 7 Thanks, I read some materials and give a proof here.
But it's pretty complicated. Your idea is nice.
Hope it helps.
【在 l*****8 的大作中提到】
: I think it's clear enough and logically true. The point here is that you
: cannot keep any previous information. Any previous numbers become unknown.
|
