Pick a random number in a pool with duplicates in O(1) time and less than O(n) space?
Why is $1$ returned with probability $33\% &lt; \frac{1}{3}$ and not with probability $\frac{30}{30+90} = \frac{1}{4}$?

Anyway, this can be done in $O(NU)$ space (assuming $i_1, \dots, i_{NU}$ each fit in $O(1)$ memory words) and $O(1)$ time (assuming you can sample an integer between $1$ and $\sum_{j=1}^{NU} i_j$ uniformly at random in $O(1)$ time) using the alias method.

The Wikipedia page includes a pseudocode that uses rational numbers (which might lead to a loss of precision, depending on their representation). If you are interested in a C++ implementation that uses integers, like in your description, see here.