分治算法的设计与分析

发布于 2023-09-13  469 次阅读


内容纲要

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 ,均不存在下标 ki < 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, 我们将其等分为两部分,leftright, 如果 left部分是漂亮数组,right 部分也是漂亮数组, 同时 left 部分全部是奇数right 部分全部是偶数,那么此时 left+right 组成的数组一定也是一个漂亮数组。

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

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

同时保证 leftright都是漂亮数组

最后递归实现

==也就是说==

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

  • N=1 时,漂亮数组为 [1]

  • N=2 时,通过 N=1变换。 1∗2−1=1,1∗2=2 所以漂亮数组为 [1,2]

  • N=3 时,通过 N=2N=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、完成情况证明

世界のネズミは彼らが望むものに依存し、彼らは彼ら自身から誰も求めません
最后更新于 2023-09-18