分治算法的设计与分析

内容纲要

1、专题名称

分治算法的设计与分析

2、实践内容

2.1 实践内容 1

（1）题目要求

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

n == nums.length
1 <= n <= 5 * 104
-10 9<= nums[i] <= 109

（2）算法设计

题目要求给出数组中大于【n/2】的元素（多数元素），若此时对数组进行排序，则数组中间的元素必定为多数元素。

（3）代码实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

（4）算法分析

时间复杂度：O(n)

空间复杂度：O(1)

算法优点：实现简单。

缺点：稍微难想一点。

2.2 实践内容 2

（1）题目要求

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：
```
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
```
示例 2：
```
输入：nums = [1]
输出：1
```
示例 3：
```
输入：nums = [5,4,-1,7,8]
输出：23
```
提示：
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104

（2）算法设计

问题可以化简为从第一个数开始，是需要加上下一个数还是直接从下一个数开始，循环遍历一次即可。

（3）代码实现

优化前

/*      超时代码，案例203/210      */
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();    // 传入数组长度
        int max_sum = nums[0];        // 输出的最大和
        for(int i = 0 ; i < n ; i++ )
        {
            int sum = 0;        // 临时和
            for(int j = i ; j < n ; j++ )
            {
                sum += nums[j];
                max_sum = max(max_sum,sum);
            }
        }
        return max_sum;
    }
};

优化后

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();    // 传入数组长度
        int max_sum = nums[0];  // 临时最大和
        int sum = nums[0];       // 最大和
        for(int i = 1 ; i < n ; i++ )
        {
            if(max_sum >= 0 && nums[i] >= 0)
            max_sum += nums[i];
            else
            max_sum = max(max_sum + nums[i],nums[i]);
            sum = max(max_sum,sum);
        }
        return sum;
    }
};

（4）算法分析

时间复杂度：O(n)

空间复杂度：O(1)

算法优点：空间复杂度低。

缺点：难想。

2.3 实践内容 3

（1）题目要求

给定整数数组 nums 和整数 k，请返回数组中第 k个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 105
-10 4<= nums[i] <= 104

（2）算法设计

手撕快速排序即可，要求高的情况下还可以基于快排再做优化。

但是过题目只需一般快速排序即可，C++已经帮我们封装好智能的sort函数了，直接调用即可。

（3）代码实现

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

（4）算法分析

时间复杂度：O(nlog2n)

空间复杂度：O(1)

算法优点：实现简单。

缺点：要学C++。

2.4 实践内容 4

（1）题目要求

如果长度为 n 的数组 nums 满足下述条件，则认为该数组是一个 漂亮数组 ：
- nums 是由范围 [1, n] 的整数组成的一个排列。
- 对于每个 0 <= i < j < n ，均不存在下标 k（i < k < j）使得 2 * nums[k] == nums[i] + nums[j] 。
给你整数 n ，返回长度为 n 的任一 漂亮数组 。本题保证对于给定的 n 至少存在一个有效答案。

示例 1 ：
```
输入：n = 4
输出：[2,1,4,3]
```
示例 2 ：
```
输入：n = 5
输出：[3,1,2,5,4]
```
提示：
- 1 <= n <= 1000

（2）算法设计

基于两个公式
$$
2*Y≠X+Z
$$

$$
奇数 + 偶数 = 奇数
$$

推导出
$$
2∗(k∗Y+b)≠k∗X+b+k∗Z+b
$$
则
$$
X,Y,Z 是一个漂亮数组，k∗X+b,k∗Y+b,k∗Z+b也一定是漂亮数组
$$

对于一个正整数 N, 我们将其等分为两部分，left 和 right，如果 left部分是漂亮数组，right 部分也是漂亮数组，同时 left 部分全部是奇数，right 部分全部是偶数，那么此时 left+right 组成的数组一定也是一个漂亮数组。

所以可以采用分治算法，自顶向下

先将数组分为两部分，将奇数放在 left，偶数放在 right

同时保证 left 和 right都是漂亮数组

最后递归实现

==也就是说==

如果我现在知道了整数 N 的漂亮数组，那么通过k∗N+b 的变换可以让 N 变成 2N的奇部（前半部分 left), 同样通过 k∗N+b 的变换可以让 N 变成 2N 的偶部（后半部分 right )，只不过 k和 b 可能取不同的值而已

N=1 时，漂亮数组为 [1]
N=2 时，通过 N=1变换。 1∗2−1=1,1∗2=2 所以漂亮数组为 [1,2]
N=3 时，通过 N=2 和 N=1 变换得到。 N=2变换得奇部 2∗1−1=1,2∗2−1=3; N=1变换得到偶部分 2∗1=2。最后漂亮数组为 [1,3,2]。始终保证奇部在前，偶部在后。

所以最后相当于是做了一个二分操作，始终寻找中点，然后将两边分治成漂亮数组。

（3）代码实现

class Solution {
public:
    unordered_map<int,vector<int> > mp;
    vector<int> beautifulArray(int n) {
        return f(N);
    }
    vector<int> f(int N) {
        vector<int> ans(N, 0);
        int t = 0;
        if (mp.find(N) != mp.end()) {
            return mp[N];
        }
        if (N != 1) {
            for (auto x : f((N+1)/2)){
                ans[t++]= 2 * x - 1;
            } 
            for (auto x : f(N/2)){
                ans[t++] =  2 * x;
            }
        }else {
            ans[0] = 1;
        }
        mp[N] = ans;
        return ans;
    }
};