Selecting random element from complement of set
Yes actually, and it's quite simple.

Sample a random integer $q$ from $[n-k]$.
Initialize $c = |\{x \in S \mid x \leq q\}|$.
While $c &gt; 0$, let $q \leftarrow q + 1$ and if $q \notin S$ decrement $c$.
Return $q$.

This works because steps 2 and 3 forms a bijective mapping from $[n -k]$ to $[n] \setminus S$. Finally the algorithm runs in $O(k)$ because it's possible to check if $q \notin S$ in $O(1)$ time either by using a $O(n)$ memory bitset or a hash table and both steps $2$ and $3$ take at most $k$ steps.