Sample K算法

0、题目来源

   最近去国内某牛叉互联网公司面试,出了一道算法题,看似简单,但是真正的答案十分巧妙。故此回忆并将原题以及解题思路记录下来,供大家学习:

随机的选取容量为N的数组中的k个元素,要求是不能重复选取,并且不能删除数组中的元素,只能够进行交换。其中 k≤n 。

1、解题思路

对于这个问题我目前有两种解法:

  1. 蓄水池算法
  2. 交换元素法

下面我就将这两种算法解决该问题的思路进行详细的解释。

1.1 蓄水池算法解题思路

  蓄水池算法的详细原理的解释和证明不是本文的重点,读者可以去百度上搜索(我发誓,我绝对会)。但是本文还是会简单的介绍一下它的大致的意思:对于一个未知大小的数组,从其中最多选取K个不重复的数据,保证每个数据被选取的概率大小完全一样。   如果你搞明白了蓄水池算法的思路,你就会明白它和本题的题意其实是完全一模一样。并且很清楚的知道它的算法复杂度为 O(n) 。

1.2 交换元素法解题思路

  第二种解题思路就更巧妙了,因为它不需要 O(n) 的复杂度,仅仅需要的是 O(k) 的复杂度。因为题目中我们知道 k≤n ,所以O(k) 的复杂度比O(n) 的复杂度更优。接下来我将解释交换元素法的原理以及必要性。

  首先,我们设想一下,如果题目不要求不重复选取的条件,那么我们很容易的想得到 O(k) 的算法。也就是依次从数组中随机的选取k个数字,不管他重复与否。但是现在题目的要求是不重复,当n很大k很小的时候,采用上述的方法也许可行,但是当k —> n 时,那时候随机选取的重复的概率将趋向于1,此法不可行。 再进一步设想,如果我们把已经选取的数据与未被选取的数据能够分隔开的话,那么这样的话,我们是不是就可以毫无顾忌的在未被选取的数据集合中进行选取而保证不会出现过重复? 答案是肯定的。 具体的做法如下:逻辑上将元素分成前n-k个元素,和最后的k个被选的元素。这样就能把元素分隔开。每次迭代的从前n-k个元素中依次选取第k个元素,此时将被选取的元素与第n-k个元素进行交换。这样就能保证,当k递增的时候,未被选取的元素总在前n-k个中,所以随机选取的时候不会出现重复的情况。而且,我们只需要k次操作就能完成所有的元素的选取,因此算法复杂度为 O(k) 。

1.3 上述两种算法优缺点

1.3.1 蓄水池算法

  1. 优点:不会改变元素的顺序;
  2. 缺点:算法复杂度高于交换元素法。

1.3.2 交换元素法

  1. 优点:算法复杂度最优;
  2. 缺点:改变了原始数组的数据出现的顺序;

所以,针对具体的问题场景和要求我们可以在上述两种算法中选择一种。

2、贴上源码(Java)

  本文题目的要求来说,算法2是最优的算法。所以给出的代码是第二种算法的实现。如果你因为对Java不熟悉看不懂源码,那么我只能说,怪我咯……

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Created by Administrator on 2017/7/23.
 */
public class Test {
    
    public static void main(String[] args) {

        int N = 100;
        int k = 50;

        // 产生一个1~100的整形数组
      List<Integer> src = new ArrayList<Integer>();
        for (int i = 0; i < N; i++) {
            src.add(i + 1);
        }

        // 定义结果数组并获取数据
        List<Integer> ans;
        ans = sample(src, k);

        // 输出结果,并检验结果
        for (int i = 0; i < ans.size(); i++) {
           System.out.print(String.format("%-5d", ans.get(i)));

            if (i % 10 == 9) {
                System.out.println();
            }
        }

    }

    public static List<Integer> sample(List<Integer> src, int k) {

        int rear = src.size();
        int index, tmp;
        Random random = new Random(System.currentTimeMillis());
        List<Integer> ans = new ArrayList<Integer>();

        for (int i = 0; i < k; i++) {

            // 随机获取数组所以并将其添加到结果数组中
            index = random.nextInt(rear);
            ans.add(src.get(index));

            // 交换数组数据
         tmp = src.get(index);
            src.set(index, src.get(rear - 1));
            src.set(rear - 1, tmp);

            // 将随机选取的数组索引下界范围前移
            rear--;
        }
        return ans;
    }
}

运行结果:

32 66 16 3 82 20 97 61 74 8

19 100 23 11 42 35 75 13 15 89

84 81 9 55 38 94 67 71 96 58

30 24 57 5 12 90 95 63 99 14

17 88 69 53 46 52 21 39 93 6

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-07-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

32410
来自专栏数据结构与算法

洛谷P2084 进制转换

题目背景 无 题目描述 今天小明学会了进制转换,比如(10101)2 ,那么它的十进制表示的式子就是 : 那么请你编程实现,将一个M进制的数N转换成十...

2123
来自专栏PaddlePaddle

【进阶篇】支持双层序列作为输入的Layer

导语 PaddlePaddle 高度支持灵活和高效的循环神经网络配置。本周进阶篇推文将围绕RNN模型展开,指导你如何在 PaddlePaddle 中配置和使用循...

27410
来自专栏Java爬坑系列

C\C++ 生成各位数不相等的随机数

  最近想写一个1A2B的小游戏来练习一下,结果在第一步生成随机数的时候就遇到了一点点问题。   游戏初始化时需要先生成一个四位随机数,且各位各不相等。于是最开...

2007
来自专栏Script Boy (CN-SIMO)

Codeforces Round #234A

Inna and choose option     题意: 一个由12个字符('O'或'X')组成的字符串,这12个字符可以排列成a*b(a*b=12)的...

2080
来自专栏ATYUN订阅号

【学术】独热编码如何在Python中排列数据?

机器学习算法不能直接处理分类数据,分类数据必须转换为数字。这适用于当你处理一个序列分类类型的问题,并计划使用深度学习方法,比如长短期循环神经网络(RNN)时。 ...

35310
来自专栏雪胖纸的玩蛇日常

4. 高等数学——元素和极限

  假设我们知道了整数的定义,像-3,1,17这些都属于整数Z。然后有理数则是两个整数相除q/p ,q,p属于Z,则是有理数Q。

752
来自专栏magicsoar

动态规划(dynamic programming)

动态规划的基本思想 动态规划的基本思想在于发现和定义问题中的子问题,这里子问题可也以叫做状态;以及一个子问题到下一个子问题之间 是如何转化的 也就是状态转移方程...

2145
来自专栏ACM算法日常

将树围起来(几何凸包)- HDU 1392

在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。如下图所示。计算凸包也就是求得外围(蓝线上)的那些点。

722
来自专栏Python攻城狮

Pandas的函数应用、层级索引、统计计算1.Pandas的函数应用apply 和 applymap排序处理缺失数据2.层级索引(hierarchical indexing)MultiIndex索引对

642

扫描关注云+社区