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.length1 <= n <= 5 * 104-109<= 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-104<= 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;
}
};（4）算法分析
时间复杂度：O(n)
空间复杂度：O(1)
算法优点：时间复杂度和空间复杂度都最优。
缺点：对数学要求极高，代码中的实现方法需要相当的C++基础，且要保证编译器支持C++11才能使用auto
3、问题与总结
问题：第四题耗时极长，看了解答也用了很长时间理解。
总结：前三道题耗时短，且所用代码极少。
4、完成情况证明
Comments NOTHING