B*******1
发帖数: 2454 | 1 Difference is Minimum
Algorithm to find the two numbers whose difference is minimum among the set
of numbers.
For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
The algorithm should return min diff = 20-19 = 1.
Constraint - Time Complexity O(N) & Space is not a constraint [upto O(3N)]
Assumption - Sorting O(nlogn) & comparison of adjacent numbers is already
known & is not an option. Try to keep it linear | d****3
发帖数: 93 | 2 坑?
这个问题至少nlogn, 可以证明的...
set
【在 B*******1 的大作中提到】
: Difference is Minimum
: Algorithm to find the two numbers whose difference is minimum among the set
: of numbers.
: For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
: The algorithm should return min diff = 20-19 = 1.
: Constraint - Time Complexity O(N) & Space is not a constraint [upto O(3N)]
: Assumption - Sorting O(nlogn) & comparison of adjacent numbers is already
: known & is not an option. Try to keep it linear
| B*******1
发帖数: 2454 | | s**x
发帖数: 405 | 4 O(n) time is impossible.
If an O(n) time algorithm for this problem exists, then such an algorithm
can also solve EDP (the Element Distinctness Problem, http://en.wikipedia.org/wiki/Element_distinctness_problem) in O(n) time.
Unfortunately EDP is proved to be Θ(nlogn). | I*********g
发帖数: 93 | 5 这个问题的特殊性在于元素是数。
solution和bucket sort 类似 | s*******f
发帖数: 1114 | 6 it may also be solved in linear expected time by a randomized algorithm that
inserts each item into a hash table and compares only those elements that
are placed in the same hash table cell.[1]
【在 s**x 的大作中提到】
: O(n) time is impossible.
: If an O(n) time algorithm for this problem exists, then such an algorithm
: can also solve EDP (the Element Distinctness Problem, http://en.wikipedia.org/wiki/Element_distinctness_problem) in O(n) time.
: Unfortunately EDP is proved to be Θ(nlogn).
| l*****a
发帖数: 14598 | 7 The internal implementation of set in STL is BST
so in fact set is already sorted...
set
【在 B*******1 的大作中提到】
: Difference is Minimum
: Algorithm to find the two numbers whose difference is minimum among the set
: of numbers.
: For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
: The algorithm should return min diff = 20-19 = 1.
: Constraint - Time Complexity O(N) & Space is not a constraint [upto O(3N)]
: Assumption - Sorting O(nlogn) & comparison of adjacent numbers is already
: known & is not an option. Try to keep it linear
| a********m
发帖数: 15480 | 8 “compares only those elements that are placed in the same hash table cell.
”这个不能保证总是线性吧。关键怎么选hashtable大小？
that
【在 s*******f 的大作中提到】
: it may also be solved in linear expected time by a randomized algorithm that
: inserts each item into a hash table and compares only those elements that
: are placed in the same hash table cell.[1]
| B*******1
发帖数: 2454 | 9 Difference is Minimum
Algorithm to find the two numbers whose difference is minimum among the set
of numbers.
For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
The algorithm should return min diff = 20-19 = 1.
Constraint - Time Complexity O(N) & Space is not a constraint [upto O(3N)]
Assumption - Sorting O(nlogn) & comparison of adjacent numbers is already
known & is not an option. Try to keep it linear | d****3
发帖数: 93 | 10 坑?
这个问题至少nlogn, 可以证明的...
set
【在 B*******1 的大作中提到】
: Difference is Minimum
: Algorithm to find the two numbers whose difference is minimum among the set
: of numbers.
: For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
: The algorithm should return min diff = 20-19 = 1.
: Constraint - Time Complexity O(N) & Space is not a constraint [upto O(3N)]
: Assumption - Sorting O(nlogn) & comparison of adjacent numbers is already
: known & is not an option. Try to keep it linear
| | | B*******1
发帖数: 2454 | | s**x
发帖数: 405 | 12 O(n) time is impossible.
If an O(n) time algorithm for this problem exists, then such an algorithm
can also solve EDP (the Element Distinctness Problem, http://en.wikipedia.org/wiki/Element_distinctness_problem) in O(n) time.
Unfortunately EDP is proved to be Θ(nlogn). | I*********g
发帖数: 93 | 13 这个问题的特殊性在于元素是数。
solution和bucket sort 类似 | s*******f
发帖数: 1114 | 14 it may also be solved in linear expected time by a randomized algorithm that
inserts each item into a hash table and compares only those elements that
are placed in the same hash table cell.[1]
【在 s**x 的大作中提到】
: O(n) time is impossible.
: If an O(n) time algorithm for this problem exists, then such an algorithm
: can also solve EDP (the Element Distinctness Problem, http://en.wikipedia.org/wiki/Element_distinctness_problem) in O(n) time.
: Unfortunately EDP is proved to be Θ(nlogn).
| l*****a
发帖数: 14598 | 15 The internal implementation of set in STL is BST
so in fact set is already sorted...
set
【在 B*******1 的大作中提到】
: Difference is Minimum
: Algorithm to find the two numbers whose difference is minimum among the set
: of numbers.
: For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
: The algorithm should return min diff = 20-19 = 1.
: Constraint - Time Complexity O(N) & Space is not a constraint [upto O(3N)]
: Assumption - Sorting O(nlogn) & comparison of adjacent numbers is already
: known & is not an option. Try to keep it linear
| a********m
发帖数: 15480 | 16 “compares only those elements that are placed in the same hash table cell.
”这个不能保证总是线性吧。关键怎么选hashtable大小？
that
【在 s*******f 的大作中提到】
: it may also be solved in linear expected time by a randomized algorithm that
: inserts each item into a hash table and compares only those elements that
: are placed in the same hash table cell.[1]
| a*****t
发帖数: 30 | 17 嗯，在想这样行不行：
设数组有N 个数A[0..N-1]，最小min, 最大max..
建立N-1个bucket, b[0],b[1]...b[N-2];
A[i]放入b[j]，j=(i-min)/(max-min) * (N-1);
同时A[i] 跟 b[j-1],b[j],b[
【在 a********m 的大作中提到】
: “compares only those elements that are placed in the same hash table cell.
: ”这个不能保证总是线性吧。关键怎么选hashtable大小？
:
: that
|
|
