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

相关文章

来自专栏机器学习算法与Python学习

机器学习(35)之PrefixSpan算法原理详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 前言 前面讲到频繁项集挖掘的关联算法...

4738
来自专栏Android机动车

数据结构学习笔记——总述

数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。

491
来自专栏云霄雨霁

排序算法总结

960
来自专栏CDA数据分析师

提升R代码运算效率的11个实用方法

众所周知,当我们利用R语言处理大型数据集时,for循环语句的运算效率非常低。有许多种方法可以提升你的代码运算效率,但或许你更想了解运算效率能得到多大的提升。本文...

1858
来自专栏轮子工厂

程序员必读:教你摸清哈希表的脾气

在哈希表中,记录的存储位置 = f (关键字),通过查找关键字的存储位置即可,不用进行比较。散列技术是在记录的存储位置和它的关键字之间建立一个明确的对应关系f ...

612
来自专栏WD学习记录

数据结构与算法2016-06-01

1.数据结构包括数据的逻辑结构和物理结构。数据的逻辑结构就是从具体问题抽象出来的数学模型,是为了讨论问题的方便,与数据在计算机中的具体存储没有关系。讨论数据结构...

792
来自专栏有趣的Python

玩转算法面试:(二)面试中的复杂度分析

面试中的时间复杂度分析 到底什么是大O n表示数据规模 O(f(n)) fn是关于n的一个函数。表示运行算法所需要执行的指令数,和f(n)成正比。 ? 常见...

5375
来自专栏osc同步分享

算法基础

分治法的基本思想: 将一个规模为 n 的问题分解为 k 各规模较小的子问题, 这些子问题互相独立且与原问题是同类型问题。 递归地解这些子问题, 然后把各个子问题...

3379
来自专栏武培轩的专栏

剑指Offer-连续子数组的最大和

题目描述 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边...

2602
来自专栏小樱的经验随笔

Wannafly模拟赛 A.矩阵(二分答案+hash)

矩阵 时间限制:1秒 空间限制:131072K 题目描述 给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出...

2715

扫码关注云+社区