0402分治算法

04.02.05 分治算法

把规模大的问题不断分解为子问题，使得问题规模减小到可以直接求解为止。分治算法从实现方式上来划分，可以分为两种：「递归算法」和「迭代算法」。

使用分治算法解决问题主要分为3个步骤：

  1. 分解：把要解决的问题分解为成若干个规模较小、相对独立、与原问题形式相同的子问题。
  2. 求解：递归求解各个子问题。
  3. 合并：按照原问题的要求，将子问题的解逐层合并构成原问题的解。

排序数组

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<int> tmp; // 声明为类成员，用于合并时临时存储

    void mergeSort(vector<int>& nums, int left, int right){
        if(left >= right){
            return;
        }
        
        int mid = (left + right) / 2;
        
        mergeSort(nums, left, mid); // 修正递归调用
        mergeSort(nums, mid+1, right);
        
        // 清空临时数组
        tmp.clear();
        
        // 合并两个有序数组
        int i = left;
        int j = mid + 1;
        while(i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                tmp.push_back(nums[i++]);
            }
            else{
                tmp.push_back(nums[j++]);
            }
        }
        
        while(i <= mid){
            tmp.push_back(nums[i++]);
        }
        while(j <= right){
            tmp.push_back(nums[j++]);
        }
        
        // 将排序好的结果复制回原数组
        for(int k = left, t = 0; k <= right; ++k, ++t){
            nums[k] = tmp[t];
        }
    }
    
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size()); // 预分配临时数组空间
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
};
  • 时间复杂度：O(logn)
  • 空间复杂度：O(n)

二分查找

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }
        }
        return -1;
    }
};
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

多数元素

哈希表

先遍历一遍数组，放入哈希表中，再遍历哈希表，找到多数元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> hash;
        for(int i = 0; i < n; i++){
            hash[nums[i]]++;
        }
        for(auto& kv : hash){
            if(kv.second > n / 2){
                return kv.first;
            }
        }
        return -1;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：哈希表，O(n)

分治法

如果 num 是数组 nums 的众数，那么我们将 nums 分为两部分，则 num 至少是其中一部分的众数。则我们可以用分治法来解决这个问题。具体步骤如下：

  1. 将数组 nums 递归地将当前序列平均分成左右两个数组，直到所有子数组长度为 1。
  2. 长度为1的子数组众数肯定是数组中唯一的数，将其返回即可。
  3. 将两个子数组依次向上两两合并。
    • 如果两个子数组的众数相同，则说明合并后的数组众数为：两个子数组的众数。
    • 如果两个子数组的众数不同，则需要比较两个众数在整个区间的众数。
  4. 最后返回整个数组的众数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    int count_in_range(vector<int>& nums, int target, int low, int high) {
        int count = 0;
        for(int i = low; i <= high; i++){
            if(nums[i] == target){
                count++;
            }
        }
        return count;
    }
    int majority_element_rec(vector<int>& nums, int low, int high) {
        // 递归结束
        if(low == high){
            return nums[low];
        }
        int mid = (low + high) / 2;
        int left = majority_element_rec(nums, low, mid);
        int right = majority_element_rec(nums, mid+1, high);
        if(count_in_range(nums, left, low, high) > (high-low+1) / 2){
            return left;
        }
        if(count_in_range(nums, right, low, high) > (high-low+1) / 2){
            return right;
        }        
        return -1;
    }
public:
    int majorityElement(vector<int>& nums) {
        return majority_element_rec(nums, 0, nums.size() - 1);
    }
};
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(logn)

投票算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

最大子数组和

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0;
        int res = nums[0];
        for(int i = 0; i < nums.size(); i++){
            pre = max(pre + nums[i], nums[i]);
            res = max(res, pre);
        }
        return res;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

分治法

维护四个变量：

  • lSum：以l为左端点的最大子段和，lSum要么等于左子区间的lSum，要么等于左子区间的iSum+右子区间的lSum，取较大值。
  • rSum：以r为右端点的最大子段和，rSum要么等于右子区间的rSum，要么等于右子区间的iSum+左子区间的rSum，取较大值。
  • mSum：[l, r]区间的最大子段和：mSum可能是左子区间的mSum，也可能是右子区间的mSum，也可能跨越左右子区间，即左子区间的rSum+右子区间的lSum。
  • iSum：[l, r]整个区间和，等于左子区间的iSum+右子区间的iSum。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    // 维护四个状态
    struct Status{
        int lSum, rSum, mSum, iSum;
    };
    // 线段树的pushup操作
    Status pushUp(Status left, Status right){
        int iSum = left.iSum + right.iSum;
        int lSum = max(left.lSum, left.iSum + right.lSum);
        int rSum = max(right.rSum, right.iSum + left.rSum);
        int mSum = max(max(left.mSum, right.mSum), left.rSum + right.lSum);
        return (Status){lSum, rSum, mSum, iSum};
    }
    // 获取子区间的和
    Status get(vector<int>& nums, int left, int right){
        if(left == right){
            return (Status){nums[left], nums[left], nums[left], nums[left]};
        }
        int mid = (left + right) / 2;
        Status lSub = get(nums, left, mid);
        Status rSub = get(nums, mid + 1, right);
        return pushUp(lSub, rSub);
    }
    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(logn)

漂亮数组

分析

漂亮数组分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> beautifulArray(int n) {
        // 递归结束
        if(n == 1){
            return {1};
        }
        vector<int> nums(n);
        for(int i = 0; i < n; i++){
            nums[i] = i + 1;
        }
        
        int leftCnt = (n + 1) / 2;
        int rightCnt = n - leftCnt;
        vector<int> left = beautifulArray(leftCnt);
        vector<int> right = beautifulArray(rightCnt);

        for(int i = 0; i < leftCnt; i++){
            nums[i] = 2 * left[i] - 1;
        }
        for(int i = 0; i < rightCnt; i++){
            nums[leftCnt+i] = 2 * right[i];
        }
        return nums;
    }
};
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(nlogn)

为运算表达式设计优先级

分治法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;
        
        // 遍历表达式查找操作符
        for(int i = 0; i < expression.length(); i++) {
            char ch = expression[i];
            // 如果当前字符是操作符，则将表达式划分为左右两部分
            if(ch == '+' || ch == '-' || ch == '*') {
                // 递归求解左右子表达式
                vector<int> leftRes = diffWaysToCompute(expression.substr(0, i));
                vector<int> rightRes = diffWaysToCompute(expression.substr(i + 1));
                
                // 对每个左右结果进行计算
                for(int left : leftRes) {
                    for(int right : rightRes) {
                        if(ch == '+') {
                            res.push_back(left + right);
                        }
                        else if(ch == '-') {
                            res.push_back(left - right);
                        }
                        else if(ch == '*') {
                            res.push_back(left * right);
                        }
                    }
                }
            }
        }
        
        // 如果 res 为空，说明没有找到任何操作符，整个表达式是一个数字
        if(res.empty()) {
            res.push_back(stoi(expression));  // 将整个表达式转换为整数
        }
        
        return res;
    }
};

  • 时间复杂度：$O(2^n)$
  • 空间复杂度：$O(2^n)$

合并k个升序链表

分析

如果只剩一个链表，就结束。然后合并两个链表，按照归并排序的方式合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 归并排序
    ListNode* mergeSort(vector<ListNode*>& lists, int left, int right){
        // 递归结束
        if(left == right){
            return lists[left];
        }
        // 一分为二
        int mid = (left + right) / 2;
        ListNode* leftList = mergeSort(lists, left, mid);
        ListNode* rightList = mergeSort(lists, mid + 1, right);
        // 合并
        return merge(leftList, rightList);
    }
    // 合并两个链表
    ListNode* merge(ListNode* leftList, ListNode* rightList){
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(leftList && rightList){
            if(leftList->val <= rightList->val){
                cur->next = leftList;
                leftList = leftList->next;
            }
            else{
                cur->next = rightList;
                rightList = rightList->next;
            }
            cur = cur->next;
        }
        while(leftList){
            cur->next = leftList;
            leftList = leftList->next;
            cur = cur->next;
        }
        while(rightList){
            cur->next = rightList;
            rightList = rightList->next;
            cur = cur->next;
        }
        return dummy->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0){
            return NULL;
        }
        return mergeSort(lists, 0, lists.size() - 1);
    }
};
  • 时间复杂度：$O(knlogk)$
  • 空间复杂度：$O(logk)$

寻找两个正序数组的中位数

分析

先用归并排序合并两个数组，然后返回中间索引的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<int> mergeSort(vector<int>& nums1, vector<int>& nums2){
        int m = nums1.size();
        int n = nums2.size();
        vector<int> res(m + n);
        int i = 0;
        int j = 0;
        int k = 0;
        while(i < m && j < n){
            if(nums1[i] <= nums2[j]){
                res[k++] = nums1[i++];
            }
            else{
                res[k++] = nums2[j++];
            }
        }
        while(i < m){
            res[k++] = nums1[i++];
        }
        while(j < n){
            res[k++] = nums2[j++];
        }
        return res;
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 合并两个数组
        vector<int> nums = mergeSort(nums1, nums2);
        // 求中位数
        int len = nums.size();
        if(len % 2){
            return nums[len / 2];
        }
        else{
            return (nums[len / 2 - 1] + nums[len / 2]) / 2.0;
        }
    }
};
  • 时间复杂度：O(m+n)
  • 空间复杂度：O(m+n)

二分算法

有点迷糊，之后再看看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 设nums1为较短的数组
        int n1 = nums1.size();
        int n2 = nums2.size();
        if (n1 > n2) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int k = (n1 + n2 + 1) / 2;
        int left = 0;
        int right = n1;
        
        while (left <= right) {  // 修改终止条件
            int m1 = (left + right) / 2;
            int m2 = k - m1;

            // 检查 m1 和 m2 的边界，确保不会越界
            if (m1 < n1 && m2 > 0 && nums1[m1] < nums2[m2 - 1]) {
                left = m1 + 1;
            } else if (m1 > 0 && m2 < n2 && nums1[m1 - 1] > nums2[m2]) {
                right = m1 - 1;
            } else {
                // 满足条件，划分完成
                int c1;
                if (m1 == 0) {
                    c1 = nums2[m2 - 1];  // nums1 全部被划分到右侧
                } else if (m2 == 0) {
                    c1 = nums1[m1 - 1];  // nums2 全部被划分到右侧
                } else {
                    c1 = max(nums1[m1 - 1], nums2[m2 - 1]);  // 左侧最大值
                }

                // 如果总数为奇数，直接返回
                if ((n1 + n2) % 2 == 1) {
                    return c1;
                }

                // 否则，计算右半部分的最小值
                int c2;
                if (m1 == n1) {
                    c2 = nums2[m2];  // nums1 全部被划分到左侧
                } else if (m2 == n2) {
                    c2 = nums1[m1];  // nums2 全部被划分到左侧
                } else {
                    c2 = min(nums1[m1], nums2[m2]);  // 右侧最小值
                }

                // 返回中位数
                return (c1 + c2) / 2.0;
            }
        }

        return 0.0;  // 理论上不会到达此处
    }
};
  • 时间复杂度：O(log min(m,n))
  • 空间复杂度：0(1)

最长公共前缀

纵向遍历

纵向遍历，从第一个字符开始，比较每一个字符串的第一个字符是否相等。若相等，则比较第二个字符，若不相等，则结束循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res = "";
        for(int i = 0; i < strs[0].length(); i++){
            char ch = strs[0][i];
            bool flag = true;
            for(int j = 1; j < strs.size(); j++){
                if((i < strs[j].length() && strs[j][i] != ch) || i >= strs[j].length()){
                    flag = false;
                    break;   
                }
            }
            if(flag){
                res += ch;
            }
            else{
                break;
            }
        }
        return res;
    }
};
  • 时间复杂度：O(mn)
  • 空间复杂度：O(1)

验证二叉搜索树的后序遍历序列

分析

可以把数组最右侧元素作为二叉搜索树的根节点值。然后判断数组的左右两侧是否符合左侧值都小于该节点值，右侧值都大于该节点值。如果不满足，则说明不是某二叉搜索树的后序遍历结果。找到左右分界线位置，然后递归左右数组继续查找。

终止条件为数组 开始位置 > 结束位置，此时该树的子节点数目小于等于 1，直接返回 True 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        int n = postorder.size();
        if(n <= 2){
            return true;
        }
        return verify(postorder, 0, n-1);
    }
    bool verify(vector<int>& postorder, int left, int right){
        // 递归结束
        if(left >= right){
            return true;
        }
        // 根是right，找到左右分界线
        int index = left;
        while(postorder[index] < postorder[right]){
            index++;
        }
        int mid = index;
        while(postorder[index] > postorder[right]){
            index++;
        }
        // 返回结果，left~mid-1是左子树，mid~right-1是右子树，right是根
        return index == right && verify(postorder, left, mid-1) && verify(postorder, mid, right-1);
    }
};
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(n)

辅助单调栈

辅助栈算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool verifyTreeOrder(vector<int>& postorder) {
        stack<int> stk;
        int root = INT_MAX;
        for(int i = postorder.size() - 1; i >= 0; i--){
            if(postorder[i] > root) return false;
            while(!stk.empty() && stk.top() > postorder[i]){
                root = stk.top();
                stk.pop();
            }
            stk.push(postorder[i]);
        }
        return true;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

总结

分治算法

算法笔记 > 分治
#leetcode-notes
0402分治算法
http://example.com/2024/09/03/posts/0402分治算法/
作者
Xuan Yang
发布于
2024年9月3日
许可协议