乐趣区

关于java:面试题精选数据伪造

这道题应该算是我原创的的一道题,来源于我遇到的一个具体需要。大抵需要是已知一批数和每个数呈现的次数,而后写个接口,每次调用都能返回已知数据中的某个数,且返回的概率和原始数据中每个数呈现的概率统一,题目形容起来有些绕口,咱们来举个理论的例子。

以下面的输出为例,要求实现的接口必须以 11.96% 的概率返回 5、18.10% 的概率返回 91……16.55% 的概率返回 98,当然我的要求不仅仅是这几个数,而是可能有 10^5 个数。先别急着往下看,给你几分钟先思考下。

各种语言其实都内置了 random 函数,能够随机返回 int 或者 long 型的随机数,这里咱们先不思考溢出的问题。为了不便解说,假如咱们已有 n 个数存在在 num[n] 中,其呈现的频次寄存在 fre[n] 中。借助已有的 random(),咱们很简略就能够生成 0 - n 之间的一个随机数 i,然而如果间接返回 num[i] 的话,每个数返回的概率是统一的,显著不满足咱们的需要。

其实解决方案也很简略,咱们依照每个数呈现的频次大小,将其映射成不同的区间大小,呈现的概率越大,区间越大。设想下,这些数据按不同的区间大小把一个飞镖盘分成不同的局部,咱们生成数的时候就是拿个飞镖随机扎,扎到哪个算哪个。

当然咱们能够间接用一位直线区间形容下面的二维飞镖盘模型。只须要随机生成 0 -100% 之间的数即可,假如某次随机生成的数是 0.65(65%),咱们算一下 正好对应在数字 58 对应的区间上,所以这次间接返回 58 就是了,咱们能够开始写代码了。

    int[] num; // 数字
    int[] fre; // 呈现的频次
    double[] pro;  // 呈现的概率
    int n;  // 数据量
    void init() {
        int sum = 0;
        for (int i = 0; i < n; i++) {sum += fre[i];
        }
        for (int i = 0; i < n; i++) {pro[i] = fre[i]/sum; // 计算出每个数呈现的概率 
        }
    }
    
    int getRandom() {double rp = random.getNextDouble();
        double sum = 0;
        for (int i = 0; i < n; i++) {if (sum >= r && sum + pro[i] > rp) {  // 找到命中的区间
                return num[i]; 
            }
            sum += pro[i];
        }
        return num[n-1];
    }

仿佛所有都很完满,但每次 getRandom() 的工夫复杂度是 O(n),大量的使用性能也抗不太住。有没有更好的实现形式?既然写到这里了,必然是有的。

下面代码循环中有个 sum += pro[i]; 每次计算都要累加,咱们是不是能够提前在 init() 中累加好?而后你会发现因为每次累加的数都只负数,所以 pro 是个递增序列,对于有序序列的查找 二分必然是首选。这时候咱们能够用二分重写下面代码。

    int[] num; // 数字
    int[] fre; // 呈现的频次
    double[] pro;  // 呈现的概率
    int n;  // 数据量
    void init() {
        int sum = 0;
        for (int i = 0; i < n; i++) {sum += fre[i];
        }
        for (int i = 0; i < n; i++) {pro[i] = fre[i]/sum; // 计算出每个数呈现的概率
            if (i != 0) {pro[i] += pro[i-1];
            }
        }
    }

    int getRandom() {double rp = random.getNextDouble();
        int l = 0;
        int r = n-1;
        while (l != r) {   // 二分查找确定区间地位  
            int mid = (l + r) >> 1;
            if (pro[mid] < rp) {l = mid + 1;} else {r = mid;}
        }
        return num[n-1];
    }

到这里问题就彻底解决了,然而最初给大家留下一个思考题。

上述代码中 pro[] 的计算有必要吗?是否间接用 fre[] 代替其性能?

退出移动版