Как получить случайный элемент из реализованного множества? - PullRequest
Новая
       70

Как получить случайный элемент из реализованного множества?

0 голосов
/ 03 апреля 2020

Я реализую свой собственный набор под названием RandomizedSet, используя технику, называемую открытое хеширование. Мне нужно создать функцию, которая возвращает мне случайный элемент в моем наборе, с условием, что все элементы должны иметь одинаковую вероятность выбора, а среднее значение этой функции должно составлять O (1) раз. Вот так выглядит мой код.

Мой класс SetNode 

class SetNode{
    int val;
    SetNode next;

    public SetNode(int x){
        val = x;
    }
}

Мой класс RandomizedSet 

class RandomizedSet {
    int size;
    ArrayList<SetNode> buckets;
    int numBuckets;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        size = 0;
        numBuckets = 10;
        buckets = new ArrayList<>();
    }

    /** Returns the index in the ArrayList where the value will be found */
    public int getBucketIndex(int val){
        String str = Integer.parseInt(val);
        int hashcode = Math.abs(str.hashCode());
        return hashcode % numBuckets;
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        int index = getBucketIndex(val);
        SetNode head = buckets.get(index);

        while(head != null){
            if(head.val == val){
                return false;
            }
            head = head.next;
        }

        size++;
        head = buckets.get(index);
        SetNode temp = new SetNode(val);
        temp.next = head;
        buckets.set(index, temp);

        if((1.0*size)/numBuckets >= 0.7){
            doubleSize();
        }

        return true;
    }

    /** Doubles the size of the ArrayList to include more nodes */
    public doubleSize(){
        ArrayList<NodeSet> temp = buckets;
        buckets = new ArrayList<>();
        numBuckets = 2*numBuckets;
        for(int i = 0; i < numBuckets; i++){
            buckets.add(null);
        }
        for(SetNode s : temp){
            SetNode head = s;
            while(head != null){
                insert(head.val);
                head = head.next;
            }
        }
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        int index = getBucketIndex(val);
        SetNode head = buckets.get(index);
        SetNode prev = null;

        while(head != null){
            if(head.val == val){
                break;
            }
            prev = head;
            head = head.next;
        }

        if(head == null){
            return false;
        }

        size--;
        if(prev != null){
            prev.next = head.next;
        }
        else{
            buckets.set(index, head.next;)
        }
        return true;

    }

    /** Get a random element from the set. */
    public int getRandom() {
    }
}

Моя основная идея сделать функцию getRandom() заключалась в генерации случайное число от 0 до numBuckets, но это не сработает, поскольку у меня могут быть пустые сегменты (заполненные нулями) и множество элементов в одном блоке, поэтому вероятность не будет равной.

Есть мысли о том, как я могу подойти к этому?

1 Ответ

0 голосов
/ 03 апреля 2020

Я довольно новичок в Java, но я почти уверен, что это должно сработать. Создайте время l oop и сгенерируйте целые числа, как вы. Как только вы найдете ведро, в котором есть значения, то сломайте время l oop. Это также должно иметь равное распространение случайности. 

public int getRandom() {
    while (true) {
        int random = (int) (Math.random() * (buckets.size() + 1));
        if (buckets.get(random) != null) {
                return random;
        }
    }
}
...