算法设计与分析-hw01

2-7

解： 原问题实际上是要计算以 $n_1,\cdots,n_d$为根的多项式的各系数，使用分治法：

$$\begin{equation*} P(x)=\prod_{i=1}^{d}\left(x-n_{i}\right)=\prod_{i=1}^{\lfloor d/2\rfloor}\left(x-n_{i}\right)\prod_{i=\lfloor d/2\rfloor+1}^{d}\left(x-n_{i}\right)=P_{1}\left(x\right)P_{2}\left(x\right) \end{equation*}$$

记次数为 $d$ 的多项式所需时间为 $T(d)$，可得如下递推公式：

$$\begin{equation*} T(d)=\begin{cases} O(1)&\quad d=1\\ 2T(d/2)+O(d \log d)&\quad d>1 \end{cases} \end{equation*}$$

设 $d = 2^t$，于是有

$$\begin{align*} T(d) &= T(2^t) = 2T(2^{t-1}) + O(2^t \log 2^t) \\ &= \cdots = 2^t T(1) + \sum_{k = 1}^{t} 2^{t-k} O(2^k \log 2^k) \\ & = O(d) + \sum_{k = 1}^{t} O(k \cdot 2^t) = O(d) + O(d) \cdot \sum_{k = 1}^{t} O(k) \\ & = O(d) + O(d) \cdot O(t^2) = O(d \log^2 d) \end{align*}$$

2-9

解： 如果数组存在主元素 $x$，由于 $|S(x)| > n/2$，所以 $x$
必定是数组的中位数。因此我们先找出原数组的中位数，再验证它是否是主元素即可。

寻找数组中位数的算法时间复杂度为 $O(n)$，得到中位数 $x_0$；然后再遍历一遍数组，统计 $x_0$ 在数组中出现的次数，这个操作时间复杂度也是 $O(n)$。上述算法总体的时间复杂度是 $O(n)$，符合题意。

2-10

O(nlogn)算法

采用分治法。

如果数组存在主元素 $x$，由于 $|S(x)| > n/2$，所以 $x$ 必定是数组中出现次数最多的数（众数）；并且，如果将原数组划分为规模相近的两部分，由抽屉原理，这个众数必定至少是某一部分的众数，我们称具有这种特殊性质的众数为“大众数”。设 $T(n)$ 为找到（或否定）长度为 $n$ 的数组中主元素所耗费的计算时间，$H(n)$ 为找到长度为 $n$ 的数组中“大众数”所耗费的计算时间。

对于一个长度为 $n$ 的数组，为了找到其“大众数” $x_0$，我们将其划分为规模相近的两部分，分别找出两部分的“大众数” $x_1,x_2$（可能相同也可能互异）。然后再将整个数组扫描一遍，计算出这两个“大众数”分别在整个数组中出现的次数，出现次数较多的那个即为 $x_0$，扫描过程需要花费 $O(n)$ 的时间开销。于是有下面的递推，

$$\begin{equation*} H(n)= \begin{cases} O(1)&\quad n\leqslant4\\ 2H(n/2)+O(n)&\quad n>4 \end{cases} \end{equation*}$$

由主定理，

$$\begin{equation*} H(n) = O(n \log n) \end{equation*}$$

由上面的论述，判断“大众数”是否为主元素，只需验证它在整个数组中出现次数是否大于 $n/2$ 即可，扫描一遍数组产生 $O(n)$ 的时间开销，于是，

$$\begin{equation*} T(n) = H(n) + O(n) = O(n \log n) \end{equation*}$$

代码实现

#include <iostream>
#include <vector>

using namespace std;

// 查找众数
double findMode(vector<double>& nums, int left, int right)
{
    if (left == right) // 只有一个元素
        return nums[left];
    int mid = (left + right) / 2; // 取中间元素
    double leftMode = findMode(nums, left, mid); // 递归左半边
    double rightMode = findMode(nums, mid+1, right); // 递归右半边
    if (leftMode == rightMode) // 左右两边众数相同
        return leftMode;
    int leftCnt = 0, rightCnt = 0; // 计数
    for (int i = left; i <= right; i++)
    {
        if (nums[i] == leftMode)
            leftCnt++;
        if (nums[i] == rightMode)
            rightCnt++;
    }
    if (leftCnt > rightCnt)
        return leftMode;
    else
        return rightMode;
}

class Solution {
  public:
    double findMainElement(vector<double>& nums) {
        int n = nums.size(); // 数组大小
        double res; // 记录主元素
        res = findMode(nums, 0, n-1); // 调用函数

        // 统计众数出现的次数，检验是否超过n/2
        int cnt = 0; // 复位
        for (int i = 0; i < n; i++)
            if (nums[i] == res)
                cnt++;
        if (cnt > n/2)
            return res;
        else
            return INT_MAX;
    }
};

int main() {
    Solution s;
    vector<double> nums = {3,2,1,2,3,2,3};
    cout << "Main element: " << s.findMainElement(nums) << endl;
    return 0;       
}

/*
实例1：（一个元素）
输入：nums = [1]
输出：1

实例2：（奇数个）
输入：nums = [3,2,1,3,3,2,3]
输出：3

实例3：（偶数个）
输入：nums = [1,3,1,1,2,1]
输出：1

实例4：（奇数个，无主元素）
输入：nums = [3,2,1,2,3,2,3]
输出：INX_MAX

实例5：（偶数个，无主元素）
输入：nums = [1,3,1,2,2,1]
输出：INX_MAX
*/

O(n)算法

设数组为 $A_0 [0:n-1]$，则对数组首尾元素进行两两配对：

$$A_0 [0] \leftrightarrow A_0 [n-1], A_0 [1] \leftrightarrow A_0 [n-2], \cdots , A_0 [(\lfloor n/2\rfloor)/2] \leftrightarrow A_0 [(\lfloor n/2\rfloor+1)/2]$$

如果 $n$ 是偶数则刚好完全配对，如果是奇数则剩下 $A_0 [(n+1)/2]$，它直接进入下一步。

然后对每一对二元组进行比较，判断二者是否相等：如果相等，则将其中一个写入数组 $A_1$ 中；否则对该对不进行操作，继续检查下一对。以此类推，反复进行上述操作，直至剩下一个数，这个数即为主元素。

设 $T(n)$ 为找到（或否定）长度为 $n$ 的数组中主元素所耗费的计算时间，则

$$\begin{equation*} T(n) \leq \begin{cases} O(1)&\quad n\leqslant2\\ 2T(n/2) + 1&\quad n>2 \end{cases} \end{equation*}$$

设 $n = 2^t$，于是有，

$$\begin{align*} T(n) &\leq 2T(n/2) + 1 \leq 4T(n/4) + 2 + 1 \\ &\leq \cdots \leq 2^t T(1) + \sum_{k = 1}^{t-1} 2^k \\ &= O(2^t) + 2^t - 1 = O(2^t) \\ &= O(n) \end{align*}$$

因此上述算法是线性时间的。

代码实现

#include <iostream>
#include <vector>

using namespace std;

class Solution {
  public:
    double findMainElement(vector<double>& nums) {
        int n = nums.size(); // 数组大小
        vector<double> arr(nums); // 备份数组
        int cnt = n; // 记录场上剩余元素个数
        double res; // 记录主元素
        while (cnt > 1)
        {
            // 配对，将结果写入arr中
            int cnt_temp = 0; // 记录局内配对成功的个数
            for (int i = 0; i < cnt / 2; i++)
            {
                if (arr[i] == arr[cnt-1-i]) 
                {
                    int temp = arr[i];
                    arr[cnt_temp] = temp;
                    // 配对成功，进入下一轮
                    cnt_temp ++;
                }
                if (cnt % 2 != 0)
                {
                    // 奇数个，则中间元素直接进入下一轮
                    arr[cnt_temp] = arr[cnt/2 + 1];
                    cnt_temp ++;
                }                
            }
            cnt = cnt_temp; // 下一局的数组长度
        }
        if (cnt == 1) // 可能是众数，还需检验
            res = arr[0];
        else // 无主元素
            return INT_MAX; 

        // 统计主元素出现的次数，检验是否超过n/2
        cnt = 0; // 复位
        for (int i = 0; i < n; i++)
            if (nums[i] == res)
                cnt++;
        if (cnt > n/2)
            return res;
        else
            return INT_MAX;
    }
};

int main() {
    Solution s;
    vector<double> nums = {1,3,1,2,2,1};
    cout << "Main element: " << s.findMainElement(nums) << endl;
    return 0;       
}

/*
实例1：（一个元素）
输入：nums = [1]
输出：1

实例2：（奇数个）
输入：nums = [3,2,1,3,3,2,3]
输出：3

实例3：（偶数个）
输入：nums = [1,3,1,1,2,1]
输出：1

实例4：（奇数个，无主元素）
输入：nums = [3,2,1,2,3,2,3]
输出：INX_MAX

实例5：（偶数个，无主元素）
输入：nums = [1,3,1,2,2,1]
输出：INX_MAX
*/

2-28

采用递归方法。

设 $T(n)$ 为找出上述 $2n$ 个数的中位数的时间开销。
对于问题 $X[left1,right1],Y[left2,right2]$，分别计算 X、Y 两数组的中位数 $x,y$，找出中位下标 $m1 = \lfloor (left1 + right1) / 2\rfloor , \lfloor m2 = (left2 + right2) / 2 \rfloor$。若 $x = y$，则返回 $x$。

否则，不妨设 $x < y$（$x > y$ 的情形同理）

$y$ 左侧的元素是 $X[left1,right1],Y[left2,right2]$ 中最大的元素，$x$ 右侧的元素是 $X[left1,right1],Y[left2,right2]$ 中最小的元素，于是将两端元素同时舍去（需要分奇偶讨论，保证删去元素数量一致）。原问题被转化为求解子问题 $X[m1+1,right1], Y[left2,m2]$（或 $Y[left2,m2-1]$）

上述过程中，查找了 $X、Y$ 数组中的中位元素，时间复杂度为 $O(1)$；每步将原问题规模缩小 1/2。所以

\begin{equation*} T(2n) = T(n) + T(n) = 2T(n/2) + O(1) \begin{cases} O(1)&\quad n=1\\ T(n/2)+O(1)&\quad n>1 \end{cases} \end{equation*} 令 $n = 2^t$，有 \begin{align*} T(n) &= T(2^t) = T(2^{t-1}) + O(1) + = \cdots \\ &= T(1) + \sum_{k = 1}^{t} O(1) = O(1) + O(t)\\ &= O(\log n) \end{align*}

代码

#include <iostream>
#include <vector>

using namespace std;

// 单数组中位数
double Median(vector<double>& X, int left, int right) {
    int n = right - left + 1;
    if (n % 2 == 0) // 偶数
        return (X[left + n/2 - 1] + X[left + n/2]) / 2.0;
    else // 奇数
        return X[left + n/2];
}

class Solution{
  public:
    double findMedian(vector<double>& X, vector<double>& Y, int left1, int right1, int left2, int right2) {
        int m1 = (left1 + right1) / 2; // 中位下标
        int m2 = (left2 + right2) / 2;
        int n = right1 - left1 + 1; // 数组长度

        if (n == 1)
            return (X[left1] + Y[left2]) / 2.0;
    
        double x = Median(X, left1, right1); // X数组中位数
        double y = Median(Y, left2, right2); // Y数组中位数

        // 两数组中位数相同
        if (x == y)
            return x;
        // 两数组中位数不同
        else if (x < y)
        {
            if (n % 2 == 0) // 偶数
                return findMedian(X, Y, m1+1, right1, left2, m2);
            else
                return findMedian(X, Y, m1+1, right1, left2, m2-1);
        }
        else
        {
            if (n % 2 == 0) // 偶数
                return findMedian(X, Y, left1, m1, m2+1, right2);
            else
                return findMedian(X, Y, left1, m1-1, m2+1, right2);
        }
    }
};

int main() {
    vector<double> X = {1, 2, 4, 4, 6};
    vector<double> Y = {2, 2, 3, 5, 5};
    int n = X.size();
    Solution s;
    double res = s.findMedian(X, Y, 0, n-1, 0, n-1);
    cout << res << endl;
    return 0;
}

/*
实例1：（单元素）
输入：
X = [1]
Y = [2]
输出：1.5

实例2：（极端情形：奇数长度）
输入：
X = [1, 2, 3, 4, 5]
Y = [6, 7, 8, 9, 10]
输出：5.5

实例3：（极端情形：偶数长度）
输入：
X = [1, 2, 3, 4, 5, 6]
Y = [7, 8, 9, 10, 11, 12]
输出：6.5

实例4：（一般情形：奇数长度）
输入：
X = [1, 3, 5, 7, 9]
Y = [2, 4, 6, 8, 10]
输出：5.5

实例5：（一般情形：偶数长度）
输入：
X = [1, 3, 5, 7, 9, 11]
Y = [2, 4, 6, 8, 10, 12]
输出：6.5

实例6：组间重复元素
输入：
X = [1, 2, 3, 4, 5]
Y = [2, 3, 4, 5, 6]
输出：3.5

实例7：组内重复元素
输入：
X = [1, 2, 4, 4, 6]
Y = [2, 2, 3, 5, 5]
输出：3.5
*/