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 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

Java 多维数组遍历

数组是Java中的一种容器对象,它拥有多个单一类型的值。当数组被创建的时候数组长度就已经确定了。在创建之后,其长度是固定的。下面是一个长度为10的数组:

821
来自专栏mathor

LeetCode325.最大子数组之和为k

 这道题暴力很好做,但是找技巧确实不好想,首先假设这么一个场景,从下标为0到下标为100,和sum = 2000,假设我们要求的目标k=800,那么我们只要...

1863
来自专栏算法channel

直接插入排序到希尔排序做的那些改进

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

3439
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继...

781
来自专栏算法channel

直接选择排序到堆排序做的那些改进

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

2867
来自专栏开发与安全

从零开始学C++之STL(四):算法简介、7种算法分类

一、算法 算法是以函数模板的形式实现的。常用的算法涉及到比较、交换、查找、搜索、复制、修改、移除、反转、排序、合并等等。 算法并非容器类型的成员函数,而是一...

1930
来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

682
来自专栏aCloudDeveloper

公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 ...

7599
来自专栏ACM算法日常

10000的阶乘-HDU1042

Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

1261
来自专栏猿人谷

对快速排序算法的分析

开篇 在实际的过程中,总需要对一些数据进行排序,在众多的排序算法中,快速排序是较为常用的排序算法之一。而网上对于快速排序的中文资料还不是很全。写 这篇博文主要记...

20210

扫码关注云+社区