两种随机抽取算法
本文最后更新于 180 天前,其中的信息可能已经有所发展或是发生改变。

洗牌算法

又名shuffle算法

背景

首先要明白这个算法的目的:打乱——等概率地穷举出所有可能的排列顺序。
就是字面意思,类似打乱一副扑克牌;实际应用可以是班级内的随机点名之类有限元随机问题

基本思想

假设有n个元素,那么由初等数学可知他们共有n! 种排序方式。
洗牌算法即模拟日常生活中的洗牌,基本操作是:从i=0处开始,每次在(i,n)之间随机选择一个数字与i进行交换,直到最后一个数字;一共会产生(n-1)x(n-2)x(n-3)x...即n! 种可能,而且是随机的。

class Solution {
    Random random = new Random();
    public int[] shuffle(int target) {
        int[] ans = target.clone();
        int n = ans.length;
        for (int i = 0; i < n; i++) {
            swap(ans, i, i + random.nextInt(n - i));
        }
        return ans;
    }
    void swap(int[] arr, int i, int j) {
        int c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }
}

水池抽样

这个算法有一些特殊的应用场景;比如说从一个十分长的队列中随机选择k个数字出来,要求每一个数字被选到的概率相同,就可以用到这种算法。

基本思想

从k=1的情况开始
也就是说,我们每次只能读一个数据。

假设数据流含有N个数,我们知道如果要保证所有的数被抽到的概率相等,那么每个数抽到的概率应该为 1/N

那如何保证呢?

先说方案:

每次只保留一个数,当遇到第 i 个数时,以 1/i的概率保留它,(i-1)/i的概率保留原来的数。

举例说明:

遇到1,概率为1,保留第一个数。
遇到2,概率为1/2,这个时候,1和2各1/2的概率被保留
遇到3,3被保留的概率为1/3,(之前剩下的数假设1被保留),2/3的概率 1 被保留,(此时1被保留的总概率为 2/3 1/2 = 1/3)
遇到4,4被保留的概率为1/4,(之前剩下的数假设1被保留),3/4的概率 1 被保留,(此时1被保留的总概率为 3/4
2/3 * 1/2 = 1/4)

以此类推,每个数被保留的概率都是1/N。可用数学归纳法证明;

接下来是k=m时:
也就是说,我们每次能读m个数据。
和上面相同的道理,只不过概率在每次乘以了m而已

图片alt

代码实现

力扣382.链表随机节点的题解

class Solution {
    ListNode head;
    Random random;

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

    public int getRandom() {
        int i = 1, ans = 0;
        for (ListNode node = head; node != null; node = node.next) {
            if (random.nextInt(i) == 0) { // 1/i 的概率选中(替换为答案)
                ans = node.val;
            }
            ++i;
        }
        return ans;
    }
}

 碎碎念

这一个问题可以说是我人生遇到的第一个算法问题了吧;
遥想当年肝了一个十一(还是五一来着)假期,在没有安卓编程基础,只会点三脚猫java的情况下,用一台手机码代码,照着各种教程,硬是码出了一个“点名器”app,送给了我们最和蔼的语文老师用来点名背古诗233333.不过当时实在是没有什么算法的概念,随机点名只是把人名存成了一个数组,每次从里面随机拿出来一个罢了;导致重复率相当的高,效果并不算好。
直到今天力扣每日一题刷到了一个蓄水池算法,突然激起了遥远的回忆哈,遂作此篇。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇