optimal way to randomly picking from a discontinuous set of numbers without duplicates

I know similar questions have already been asked, but it's slightly more specific.

I have a given range, say N = {0, ..., n - 1} with n = 720 in the worst case, a set of numbers P = {p1, p2, ...}, M = N \ P and 0 < b < n * 0.8. I want to randomly pick b numbers from set M.

My solutions this far:

ArrayList<Integer> option1(ArrayList<Integer> n, ArrayList<Integer> p, int b) {
    n.removeAll(p);
    Collections.shuffle(n);
    return new ArrayList<>(n.subList(0, b - 1));
}


ArrayList<Integer> option2(ArrayList<Integer> n, ArrayList<Integer> p, int b) {
    n.removeAll(p);
    ArrayList<Integer> rsl = new ArrayList<>();
    Random r = new Random();
    for(int i = 0; i < b; i++){
        int j = r.nextInt(n.size());
        n.remove(Integer.valueof(j));
        rsl.add(j);
    }
    return rsl;
}

option1 seems a bit excessive for a small b and large n, while option2 has to work on 2 lists and needs casting. I want to keep the performance as optimal as possible. I've found a couple of solutions for sets of continuous numbers, but not for discontinuous. Any ideas how to improve this?