leetcode 分治算法

分治算法入门

以下节选自 leetcode上的入门题

分治算法

所谓的分治算法通俗来讲，就是将大的问题拆解成许多单一的子问题，通过解决子问题，并合并子问题结果反推原问题。也就是递归的思想。

169 多数元素

采用暴力算法，依次遍历数组中每个元素出现的次数，时间复杂度为O(n*n)，会超时。肯定不是改题目的本意。

方法一：分治思想，递归思路

采用分治思想，递归思路。
     * 1、确定切分的终止条件，直到所有的子问题都是长度为 1 的数组，停止切分。
     * 2、拆分数组，递归地将原数组二分为左区间与右区间，直到最终的数组只剩下一个元素，将其返回
     * 3、处理子问题得到子结果，并合并
     *    3.1 长度为 1 的子数组中唯一的数显然是众数，直接返回即可。
     *    3.2 如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。
     *    3.3 如果他们的众数不同，比较两个众数在整个区间内出现的次数来决定该区间的众数

代码实现：

public class Main {
    /**
     * 采用分治思想，递归思路。
     * 1、确定切分的终止条件，直到所有的子问题都是长度为 1 的数组，停止切分。
     * 2、拆分数组，递归地将原数组二分为左区间与右区间，直到最终的数组只剩下一个元素，将其返回
     * 3、处理子问题得到子结果，并合并
     *    3.1 长度为 1 的子数组中唯一的数显然是众数，直接返回即可。
     *    3.2 如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。
     *    3.3 如果他们的众数不同，比较两个众数在整个区间内出现的次数来决定该区间的众数
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        if (nums.length < 1) return 0;
        return help(nums, 0, nums.length - 1);
    }

    private int help(int[] nums, int start, int end) {
        // 1、拆分数组，直到剩下最后一个 一定为众数
        if (start == end) return nums[start];
        // 2、处理子问题
        int mid = start + (end - start) / 2;
        int left = help(nums,start,mid);
        int right = help(nums, mid+1,end);
        //  如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。
        if (left == right)
            return left;

        // 统计左右区间的众数
        int leftCount = countElement(nums, left, start, end);
        int rightCount = countElement(nums, right, start, end);

       return leftCount > rightCount ? left : right;
    }

    private int countElement(int[] nums, int num, int start, int end) {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (num == nums[i])
                count++;
        }
        return count;
    }

    public static void main(String[] args) {
        Main test = new Main();
        int[] nums = {3,3,3,2,1};
        System.out.println(test.majorityElement(nums));
    }
}

复杂度分析

• 时间复杂度：O($nlogn$)
• 空间复杂度：O($nlogn$)。用到了递归，需要调用栈，所以复杂度为O($nlong$)

递归讲起来比较抽象，需要debug看看调用栈的信息，下面介绍个好理解的方法

方法二：HashMap

HashMap采用key-value的形式存储数据，刚好可以统计数组中各元素出现的次数。

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Main {

    public static int majorityElement(int[] nums) {

        HashMap<Integer, Integer> map = new HashMap<>();
        // 统计各元素出现的次数
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i],0) + 1);   
        }

        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer,Integer> entry : entries) {
            // 找出满足条件的众数
            if (entry.getValue() > (nums.length / 2)) {
                return entry.getKey();
            }
        }
        return 0;   // 题目描述一定存在，所以这块不会被执行到，返回不报错的整数即可
    }


    public static void main(String[] args) {
        int[] nums = {3,3,3,2,1};
        System.out.println(Main.majorityElement(nums));;
    }
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n). 哈希表中最多包含 n - n/2个键值对，所以占用空间为O(n). 题目保证一定有一个众数，而一个长度为n的数组最多只包含n个不同的值，会占用n/2 + 1个数字，所以最多有n-(n/2+1)个不同的其他数字，所以最多有n-n/2(取整)个不同的元素。

更多方法参考：leetcode讨论区

53. 最大子序和

方法一：暴力算法

public int maxSubArray(int[] nums) {
    int res = Integer.MIN_VALUE;   // 每次遍历寻找最大子序和
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;  // 用来保存子序列的和
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            res = Math.max(res, sum);
        }
    }
    return res;
}

复杂度分析：

• 时间复杂度：O(N*N)
• 空间复杂度：O(1)

方法二：动态规划

第 i 个子组合的最大值可以通过第i-1个子组合的最大值和第 i 个数字获得，如果第 i-1 个子组合的最大值没法给第 i 个数字带来正增益，我们就抛弃掉前面的子组合，自己就是最大的了。

public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    dp[0] = nums[0]; // 初始化
    for (int i = 1; i < nums.length; i++) {
        // 状态转移方程
        if (dp[i-1] >= 0) {
            dp[i] = dp[i-1] + nums[i];
        } else {
            dp[i] = nums[i];
        }
    }

    // dp数组中记录了所有的子序列的和，找出最大的即可
    int res = Integer.MIN_VALUE;
    for (int i = 0; i < dp.length; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
}

结合本题，可以进一步优化，具体如下：

public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (sum >= 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
            res = Math.max(res, sum);
        }
        return res;
    }

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

方法三：分治法

类似于归并排序，先切分后合并

public int maxSubArray(int[] nums) {
    return maxSubArrayDivideWithBorder(nums, 0, nums.length-1);
}

private int maxSubArrayDivideWithBorder(int[] nums, int start, int end) {
    // 递归终止条件，只有一个元素的时候
    if (start == end) return nums[start];

    int mid = start + (end - start) / 2;
    int leftMax = maxSubArrayDivideWithBorder(nums, start, mid);
    int rightMax = maxSubArrayDivideWithBorder(nums, mid + 1, end);

    // 下面计算横跨两个子序列的最大值
    // 计算包含左侧子序列最后一个元素的子序列最大值
    int leftCrossMax = Integer.MIN_VALUE;
    int leftCrossSum = 0;
    for (int i = mid; i >= start; --i) {
        leftCrossSum += nums[i];
        leftCrossMax = Math.max(leftCrossMax, leftCrossSum);
    }

    // 计算包含右侧子序列最后一个元素的子序列最大值
    int rightCrossMax = nums[mid + 1];
    int rightCrossSum = 0;
    for (int i = mid + 1; i <= end; i++) {
        rightCrossSum += nums[i];
        rightCrossMax = Math.max(rightCrossMax, rightCrossSum);
    }

    // 计算跨中心的子序列的最大值
    int crossMax = leftCrossMax + rightCrossMax;

    return Math.max(crossMax, Math.max(leftMax, rightMax));
}

复杂度分析：

• 时间复杂度：O($nlogn$)
• 空间复杂度：O($logn$)

参考：leetcode讨论区

50、Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

思路：

public double myPow(double x, int n) {
    if (x == 0.0) return 0.0;
    double res = 1.0;
    boolean isP = true;  // 判断是否为正数
    if (n < 0) {
        isP = false;
        n = -n;
    }

    while (n != 0) {
        if ((n&1) == 1) {  // 等价于 n % 2 == 1 奇数
            res *= x;
        }
        x *= x;  // 等价于 x = x^2;
        n /= 2;  // 减半
    }
    return isP?res:1/res;
}

复杂度分析：

• 时间复杂度：O($logn$)
• 空间复杂度：O(1)

套路：

leetcode 分治算法

原文：https://www.cnblogs.com/guohaoblog/p/13521120.html