每日算法题：Day 25（概率统计）

Day 25, 概率统计知识点走起~

1

编程题

【剑指Offer】数组中重复的数

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路： 由于题目中说了数组的长度为n，且每个数都在0到n-1的范围内，那么如果这个数组是排好序的，则每个数字与其索引数应该是相等的。因此我们遍历整个数组，判断每一个位置的值和其索引相不相等，如果相等，则遍历下一个位置。

如果不相等，那么会进入一个循环，在循环中，会判断number[i]和number[number[i]]两个数是否相等，如果相等，则找到一对重复的，退出！，否则交换当前值number[i]和number[number[i]]两个数，这样就使得number[i]这个数回到了自己的位置，就这样一直循环直到number[i] == i，即i位置的索引与值相同！

class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        if(numbers == nullptr || length <= )
            return false;

        for(int i = ;i < length; ++i){
            if(numbers[i]< || numbers[i] >= length)
                return false;    //输入数据边界判断

            while(numbers[i] != i){
                if(numbers[i] == numbers[numbers[i]]){   
                    //当每个数位置确定，则可以找出任意的重复数字
                    *duplication = numbers[i];
                    return true;
                }
                swap(numbers[i], numbers[numbers[i]]);
            }
        }
        return false;
    }
};

【剑指Offer】构建乘积数组

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]A[i+1]…A[n-1]。不能使用除法。

思路：

我们可以看上面的图片，我们可以使用一个和A数组一样大小的b数组，首先计算下三角的乘积，只需要O(n)的时间可以遍历得到一个b[n]的数组，包含下三角的乘积，对角线元素值为1。然后接着对上三角进行乘积，也可以使用O(n)的时间获得其对应的值并于原来的b数组对应相乘，就可以得到答案，总复杂度为2O(n)，忽略常数项即为O(n)的时间！效率非常高了！

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int size = A.size();
        vector<int> b(size);
        int res = ;
        for(int i = ;i < size; i++){  
            b[i] = res;   // 计算下三角的值b[n-1] = A[0]*...*A[n-2];
            res *= A[i];
        }
        res = ;
        for(int i = size-1;i >= ; i--){
            b[i] *= res;  // 计算上半角b[0] = b[0]*...*A[n-1]
            res *= A[i];
        }
        return b;
    }
};

2

概念题

【概率统计】所有人口中，某癌症的患病率为0.008。对有癌症的病人，医院的化验测试有2%的可能错判其无癌症。对无癌症的病人，有3%的可能错判其有癌症。问：现有一新病人，化验测试表明其有癌症，该病人实际患有癌症的概率是多少？（计算过程四舍五入保留4位小数）

这其实很类似于TP和FP的概念，其中TP为化验为癌症且确实患有癌症的概率为：0.00898%，FP为化验为癌症但却没有癌症的概率为：0.9923%，因此化验为癌症的总概率为(0.00898%+0.9923%). 最后总的概率为0.00898% / (0.00898%+0.992*3%)。

【概率统计】参加支付宝夜谈分享的同学共有50人，现设有甲、乙、丙三个夜谈主题。有40人选择参加甲夜谈主题，36人选选择参加乙夜谈主题，30人选择参加丙夜谈主题，兼选甲乙夜谈主题的有28人，兼选甲丙夜谈主题的有26人，兼选乙丙两门夜谈主题的有24人，甲乙丙三个夜谈主题均选的有20人，问三个夜谈主题未选的有多少人？

这个题目如果使用文氏图的话，一目了然，我们根据题目所给的条件将文氏图从里到外填写完整，三个圆圈代表对应得甲乙丙三个夜谈主题，然后将所有的人数进行相加即可！

相加之后得人数为48，也就是说只有两个人三个夜谈主题未选。

【概率统计】20个阿里巴巴B2B技术部的员工被安排为4排，每排5个人，我们任意选其中4人送给他们一人一本《effective c++》，那么我们选出的4人都在不同排的概率为？

由于题目要求选取得人不同排，因此我们先分成4组，从每组任意选取1个人，即C(5,1)C(5,1)C(5,1)*C(5,1)，然后再对这4个人进行全排列，A(4,4)，剩余得16人进行全排列A(16,16). 因此概率为：

C(5,1) * C(5,1) * C(5,1) * C(5,1) * 4！*16！/ 20！