等確率ランダム取数アルゴリズム-シャッフルアルゴリズム|チェーンテーブルランダムノード|ランダム数インデックス-Java実装

目次
1.シャッフルアルゴリズム
シャッフルアルゴリズムJava実装
複雑度分析
かくりつぶんせき
2.チェーンテーブルランダムノード
問題解Java実装
複雑度分析
かくりつぶんせき
3.乱数索引
問題解Java実装
複雑度分析
かくりつぶんせき
1.シャッフルアルゴリズム
1.1 Mサイズの配列からランダムに1つの数を選択する方法
最も考えやすい方法は、Randomを用いて[0-(M-1)]の範囲の値をランダムにし、配列内の対応するインデックスの値をとることです.
1.2 Mサイズの配列から、N個の重複しない数をランダムに選択する方法
ループ->(Randomメソッドで[0-(M-1)]の範囲の値をランダムにし、配列から対応するインデックスの値を探します)
この場合、乱数は繰り返され、選択された数を記録することができ、乱数が選択された場合、N個の重複しない数が選択されるまで選択を継続することができる.
以上の方法では,NとMが近接してランダムに出てくる数が多いほど,数値が繰り返される確率が高くなり,時間的複雑度も高くなる.
 
上記NがMに近い場合の処理方法については,配列中の要素を順番に乱すことを考慮し,インデックス値が0−(N−1)のN個数を選択することができる.
配列を乱すプロセスを保証する必要があります.すべての要素がインデックス位置にある確率が等しいことを保証する必要があります.
この乱れ過程は等確率アルゴリズムであり,典型的な等確率アルゴリズムはトランプアルゴリズムである.
 
シャッフルアルゴリズムJava実装

public static void main(String[] args) {
    int[] cards = new int[54];
    for (int i = 0; i < cards.length; i++) {
        cards[i] = i;
    }

    System.out.println("    = " + Arrays.toString(cards));
    Shuffle shuffle = new Shuffle();
    shuffle.shuffle(cards);
    System.out.println("    = " + Arrays.toString(cards));
}

/**
 *     
 */
public void shuffle(int[] cards) {
    Random random = new Random();
    for (int i = cards.length - 1; i >= 0; i--) {
        swap(cards, i, random.nextInt(i + 1));
    }
}

public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

 
複雑度分析
時間複雑度:配列を1回だけループし,時間複雑度はO(n)であった.
空間複雑度:定数級空間を用い,空間複雑度はO(1)である.
 
かくりつぶんせき
上記のコードでは、トランプの54枚のトランプをシミュレートするために1～54の数字を使用します.
任意のインデックスk(0<=k<=53)について,配列乱れ後に位置する各位置の確率を計算する.
 
乱したkインデックスの値がインデックス53の位置にある確率
すなわち,1回目のランダム生成数はk,kと53が交換され,確率は1/54である.
 
乱したkインデックスの値がインデックス52の位置にある確率
まずkはインデックス53の位置ではなく,2回目のランダム生成数はk,kは52と交換され,確率は53/54*1/53=1/54である.
......
乱した後のkインデックスの値がインデックスxの位置にある確率
まずkはインデックス53の位置ではなく、インデックス52の位置ではない.......kインデックスxの位置
確率=53/54*52/53*51/52*...*  (x+1)/(x+2) * 1/(x+1) = 1/54 
 
トランプアルゴリズムは配列中の任意の値が配列が乱れた後,任意の位置に現れる確率が1/nであることを保証した.
 
2.チェーンテーブルランダムノード
この問題は力ボタン382題:チェーンテーブルランダムノード(https://leetcode-cn.com/problems/linked-list-random-node/)
単一チェーンテーブルが与えられ、チェーンテーブルのノードがランダムに選択され、対応するノード値が返されます.各ノードが選択される確率が同じであることを保証します.
ステップアップ:チェーンテーブルが非常に大きく、長さが不明な場合、この問題をどのように解決しますか?定数レベルの空間複雑度を使用して実現できますか?
例:

//          [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

Solution solution = new Solution(head);
// getRandom()       1,2,3    ，              。
solution.getRandom();

 
問題解Java実装
 

public Solution(ListNode head) {
    this.head = head;
}

public int getRandom() {
    int val = 0;
    //       
    int count=0;
    //        
    ListNode node = head;
    
    Random random = new Random();

    while(node!=null){
        //      ，      +1
        count++;
        //   [0,count)       ，      0  ，           
        //      0      1/count
        if(random.nextInt(count)==0){
            val = node.val;
        }
        node = node.next;
    }

    return val;
}

 
複雑度分析
時間複雑度:単一チェーンテーブルを1回だけ遍歴し,時間複雑度はO(n)であった.
空間複雑度:定数級空間を用い,空間複雑度はO(1)である.
 
かくりつぶんせき
n個のノードを含む単一チェーンテーブル
1番目のノードを選択する確率
=1番目のノードを選択する確率*2番目のノードを選択しない確率*3番目のノードを選択しない確率*n番目のノードが選択されない確率
= 1 * 1/2 * 2/3 * ... * n-1/n = 1/n
 
2番目のノードを選択する確率
=2番目のノードを選択する確率*3番目のノードを選択しない確率*4番目のノードを選択しない確率*n番目のノードが選択されない確率
= 1/2 * 2/3 * 3/4 * ... * n-1/n = 1/n
......
k番目のノードを選択する確率
=k番目のノードが選択される確率*k番目+1番目のノードが選択されない確率*k番目+2番目のノードが選択されない確率*n番目のノードが選択されない確率
= 1/k * k/k+1 * k+1/k+2 * ... * n-1/n = 1/n
 
n番目のノードを選択する確率
= 1/n
 
n個のノードを含む単一チェーンテーブルでは,各ノードが選択される確率は1/nであり,確率は等しい.
 
3.乱数索引
この問題は力ボタン398題:乱数インデックス(https://leetcode-cn.com/problems/random-pick-index/)
重複要素を含む可能性のある整数配列を指定し、指定した数値のインデックスをランダムに出力する必要があります.与えられた数値が必ず配列に存在すると仮定できます.
注意:配列のサイズは非常に大きい場合があります.余分なスペースを使用しすぎるソリューションは、テストに合格しません.
例:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3)        2,3    4。             。
solution.pick(3);

// pick(1)      0。    nums[0]  1。
solution.pick(1);

 
問題解Java実装

public int pick(int target) {
    Random random = new Random();
    //        
    int index = 0;
    //      target         
    int n = 0;

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            //        == target，           +1
            n++;
            //            ，  ==0        ，  !=0         
            if (random.nextInt() % n == 0) {
                index = i;
            }
        }
    }

    return index;
}

 
複雑度分析
時間複雑度:配列のみを1回サイクルし,時間複雑度はO(n)であった.
空間複雑度:定数級空間を用い,空間複雑度はO(1)である.
 
かくりつぶんせき
タイトルの例:solution.pick(3);
3が存在するインデックスは2,3,4であり、条件を満たすインデックスの個数はn=3である.
 
インデックスが2の確率を返します.
インデックス2を返す確率=インデックス3が選択されていない確率*インデックス4が選択されていない確率=1/2*2/3
インデックス2を選択する確率は1/3です
インデックスが3になる確率を返します.
インデックス3の前のインデックスが選択されているかどうかを考慮する必要はありません.インデックス3が選択されている確率*インデックス3の後のインデックスが選択されていない確率だけでいいです.
インデックス3を返す確率=インデックス3を選択する確率*インデックス4を選択しない確率=1/2*2/3
インデックス3を選択する確率は1/3です
 
インデックスが4の確率を返します.
最後のインデックスは、前にどのインデックスを選択しても影響しません.最後のインデックスが選択された確率を計算するだけです.
インデックス4を返す確率=インデックス4を選択する確率=1/3
インデックス4を選択する確率は1/3
 
複数の条件を満たすn個のインデックスに対して、各インデックスが選択される確率は1/nであり、確率は等しい