面试题精选:数据伪造

左手的ㄟ右手 2021-09-24 16:16 351阅读 0赞

这道题应该算是我原创的的一道题，来源于我遇到的一个具体需求。大致需求是已知一批数和每个数出现的次数，然后写个接口，每次调用都能返回已知数据中的某个数，且返回的概率和原始数据中每个数出现的概率一致，题目描述起来有些绕口，我们来举个实际的例子。  
![在这里插入图片描述][20200913190025916.png_pic_center]  
以上面的输入为例，要求实现的接口必须以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\]的话，每个数返回的概率是一致的，明显不满足我们的需求。

其实解决方案也很简单，我们按照每个数出现的频次大小，将其映射成不同的区间大小，出现的概率越大，区间越大。想象下，这些数据按不同的区间大小把一个飞镖盘分成不同的部分，我们生成数的时候就是拿个飞镖随机扎，扎到哪个算哪个。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center]  
当然我们可以直接用一位直线区间描述上面的二维飞镖盘模型。只需要随机生成0-100%之间的数即可，假设某次随机生成的数是0.65(65%)，我们算一下 正好对应在数字58对应的区间上，所以这次直接返回58就是了，我们可以开始写代码了。  
![在这里插入图片描述][20200913191820378.png_pic_center]

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\[\]替代其功能？

[20200913190025916.png_pic_center]: /images/20210923/3aa9c7ecf9ae46d58d13ffe76e867e8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbmRvbw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/35687213bccb451b9ce1c478d456e558.png
[20200913191820378.png_pic_center]: /images/20210923/47c6a4f1a11341fe9f34006e9d041cad.png