当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

有一个数组,每次从中间随机取一个,然后放回去,当所有的元素都被取过,返回总共的取的次数。写一个函数实现。复杂度是什么。

发表于: 2012-12-07   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Random; import java.util.Set; import java.util.TreeSet; /** * http://weibo.com/1915548291/z7HtOF4sx * #面试题#有一个数组,每次从中间随机取一个,然后放回去,当所有的元素都被取过,返回总共的取的次数。 * 写一个函数实现。复杂度是什么

import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

/**
 * http://weibo.com/1915548291/z7HtOF4sx
 * #面试题#有一个数组,每次从中间随机取一个,然后放回去,当所有的元素都被取过,返回总共的取的次数。
 * 写一个函数实现。复杂度是什么。
 * 
 * 我认为这道题的考点是如何节省空间。
 * 当然可以用一个与原数组长度相同的数组来标记对应元素是否被取过,但这样太浪费空间
 * 用bitmap的话,只要一个bit就可以标记是否被取过,可参考《编程珠玑》的位图排序
 * 
 * 时间复杂度的话,我不太会算,以下是引用https://github.com/vyan/test/blob/master/accessTimes.cpp:
 * 使用bit打点记录已经取的数, 
 * 复杂度分析,假设数组总长度为n 
 * 取到第1个之前未被取到的数的期望 E(1)=1 
 * 取到第2个之前未被取到的数的期望 E(2)=n/n-1 
 * 取到第3个之前未被取到的数的期望 E(3)=n/n-2 
 * ...
 * 取到第n个之前未被取到的数的期望 E(n)=n/1 
 * 总得期望次数E=n+n/(n-1)+n/(n-2)+...+n/1;
 *              =n(1+1/(n-1)+1/(n-2)+...+1/1) 
 *              =nln(n) 
 * 所以算法平均复杂度为nlogn 
 * 
 * 下面的代码里面,除法和求模运算我都用位运算来实现(为了练习位运算),事实上直接用java提供的(/,%)也可以
 * 同时,为了验证是否真的取到了数组的所有元素,我用了TreeSet保存已选中的下标(去重)
 * 
 * 最后,还有一个问题是,可能取了很多次,都没能全选中,这个时候可以设置一个最长时间或者最大尝试次数,超过则结束程序,
 * 避免程序长时间运行甚至死循环
 * 
 * @author lijinnan
 * 
 */
public class TimesOfAccessArray {

    public static final int SHIFT = 5;
    public static final int BLOCK_SIZE = (1 << SHIFT);  //32
    public static final int MASK = (1 << SHIFT) - 1;  //31

    public static void main(String[] args) {
        int[] array = new int[200];
        long times = accessTimes(array);
        System.out.println(times);
    }
    
    public static long accessTimes(int[] array) {
        if (array == null || array.length == 0) {
            return -1L;
        }
        long result = 0L;
        int len = array.length;
        int[] bitmap = new int[divide(len, BLOCK_SIZE) + 1];
        int setTimes = 0;
        Set<Integer> set = new TreeSet<Integer>();
        while (setTimes < len) {
            int pos = new Random().nextInt(len);
            set.add(pos);
            if (set(bitmap, pos)) {
                setTimes++;
            }
            result++;
        }
        System.out.println(set);
        return result;
    }
    
    public static boolean set(int[] bitmap, int pos) {
        boolean result = false;
        int blockNo = divide(pos, BLOCK_SIZE);
        int index = mod(pos, BLOCK_SIZE);
        boolean notExist = (bitmap[blockNo] & (1 << index))== 0;
        if (notExist) {
            bitmap[blockNo] |= (1 << index);
            result = true;
        }
        return result;
    }

    public static boolean exist(int[] bitmap, int pos) {
        int blockNo = divide(pos, BLOCK_SIZE);
        int index = mod(pos, BLOCK_SIZE);
        return (bitmap[blockNo] & (1 << index)) != 0;
    }
    
    private static int divide(int x, int y) {
        return x >> offSet(y);
    }

    private static int mod(int x, int y) {
        int z = x;
        int i = offSet(y);
        return z - ((z >> i) << i);
    }
    
    //e.g. 32=2^5, return 5 只考虑2的幂
    private static int offSet(int y) {
        return howManyBits(y) - 1;
    }

    //二进制的表示里面,有多少位。例如32是6位
    private static int howManyBits(int y) {
        int bitNum = 0;
        while (y != 0) {
            y = (y >> 1);
            bitNum++;
        }
        return bitNum;
    }
   

}

有一个数组,每次从中间随机取一个,然后放回去,当所有的元素都被取过,返回总共的取的次数。写一个函数实现。复杂度是什么。

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
说到Web爬虫,Python占了半壁江山。但是Web页面不是Python的强项了,如果需要扒取Web数据,再Mashup
最近在写往公司产品里添加Tomcat适配器,以支持Tomcat。有一些功能需要摘取到Tomcat的部分日志。没
Java报表工具数据钻取在一个页面展开 有一些客户希望在一个页面打开数据钻取的全部内容,这个功能可
Table_A表是用户表,Table_B是条件表,每个用户对应多个条件,并且用户对应条件的状态有可能是true
扒网站前端,自己大多数只做后端。 火狐安装ScrapBook插件,在FIREFOX上ALT键,保存页面,ALT+K在侧
前段时间,女朋友如愿以偿的找到了销售的工作,第一天正式上班还挺高兴,第二天就开始愁眉苦脸了。
前段时间,女朋友如愿以偿的找到了销售的工作,第一天正式上班还挺高兴,第二天就开始愁眉苦脸了。
I love sneakers! Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Oth
前段时间阅读了一篇名为《 [Python]网络爬虫(八):糗事百科的网络爬虫(v0.3)源码及解析(简化更
您有在工作中有类似这样的需求吗:从10万条不重复的数据中随机取出1千条不重复的数据?这里我们通过
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号