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. |
