由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - Algorithm Question: Given an array and a sum value return
相关主题
array allocation in c请教一个C++问题
求String中递增子字符串的个数怎么解?要求O(nlogn)[转载] CS Algorithm Interview question
Check if the sum of two integers in an integer array eqauls to the given number 这段代码为何要这样做?
Efficient algorithms for finding number, help pleaseWhy Avoid array indexing. Use pointers.
一FG家常见题 (转载)An algorithm question
stack/heap corruptionGoogle 电面 algorithm 问题 (转载)
请教一道题Bandit Algorithms for Website Optimization
这个怎么allocate memory?cxx程序如何给optimized build加函数symbol?
相关话题的讨论汇总
话题: array话题: question话题: given话题: algorithm话题: min
进入Programming版参与讨论
1 (共1页)
h*****f
发帖数: 248
1
http://www.careercup.com/question?id=4129291
會有比O(nlogn)快的方法嗎?
counting sort won't work if there is duplicate...
k**********g
发帖数: 989
2
O(N) (best case O(1)) if the input values are integers and the range is
finite (and relatively small compared to the array size.)
Suppose the values in the input array are bounded, i.e. input x[k], where
MIN <= x[k] <= MAX. N is the size of input (1 <= k <= N).
Allocate an array of size (MAX - MIN + 1), that is, one element for each
possible integer value between [MIN, MAX]. Each element can contain either a
special value "UNASSIGNED", or an unsigned integer which is an index (k)
from the input array (x[k]).
Blah blah blah. (No sorting.)
Optimal time, and optimal time in the best case too because it does not need
to scan all N input elements. It finishes when the first hit is found. But
O(absdiff(MAX - MIN)) space.
1 (共1页)
进入Programming版参与讨论
相关主题
cxx程序如何给optimized build加函数symbol?一FG家常见题 (转载)
gcc 优化不优化运算结果不一样?gcc 的 bug?stack/heap corruption
effective C++里的memory pool 一问:请教一道题
why do we still use dynamic allocation?这个怎么allocate memory?
array allocation in c请教一个C++问题
求String中递增子字符串的个数怎么解?要求O(nlogn)[转载] CS Algorithm Interview question
Check if the sum of two integers in an integer array eqauls to the given number 这段代码为何要这样做?
Efficient algorithms for finding number, help pleaseWhy Avoid array indexing. Use pointers.
相关话题的讨论汇总
话题: array话题: question话题: given话题: algorithm话题: min