【LeetCode】十三、分治法：多数元素 + 最大子序列和

文章目录

1、分治法
2、leetcode169：多数元素
3、leetcode53：最大子序和

1、分治法

分治一般都搭配递归使用：

在这里插入图片描述

用分治法的一个应用——归并排序：将一组数不停的一分为二，直到分到每组只有一个数的时候

在这里插入图片描述

分到每组只有一个数的时候，到达递归终止的条件（把一个排序的大问题，分成了少量元素排序的小问题），开始倒着往回退，每层分别排序各自组里的数据，即小问题的解

在这里插入图片描述

组合小问题的解，就是最终的排序结果。比较左右两个小问题的解（有序数列）的首元素，每次比较拿出小的那个首元素放入最终的结果。 因此说：左右两边分别是有序的，那把它两合并成一个新的有序的结果是更容易的。

2、leetcode169：多数元素

在这里插入图片描述

这题本质还是要用到元素出现的次数，也就是要统计次数，首先用HashMap的数据结构，就可以解决。

这里用分治法解决一下：把一组数分成一个个不可再分的元素（分治法里所说的小问题），再分别求众数，往上开始一层回退递归，如果左边有一半以上的数是n，右边也有一半以上的数是n，那左右两边合并后，多数元素就也是n。

为什么可以用分治，因为，如果a是数组num的众数，那么将num一分为二后，至少有一边的众数也是a，因此分治得到的最终的结果是正确的。

其次，每次左右两边的众数如果相等，则这一个区间的众数就是该值，反之，左右两边的众数值不一样，那就要比较这两个众数在区间里出现的次数，来决定选谁，如果连出现的次数也一样，那就随机取一个。

举例：
在这里插入图片描述

代码实现：

public class P169 {

    public static int majorityElement(int[] nums) {
        return getMajority(nums, 0, nums.length - 1);
    }

    public static int getMajority(int[] nums, int left, int right) {
        // 数组只有一个元素了，不可再分，到达递归的终止条件
        if (left == right) {
            return nums[left];
        }
        // 一分为二，获取左右两边的多数元素
        int mid = left + (right - left) / 2;
        int leftMajority = getMajority(nums, left, mid);
        int rightMajority = getMajority(nums, mid + 1, right);
        if (leftMajority == rightMajority) {
            return leftMajority;
        }
        // 左右两边的多数元素结果不相等，统计次数
        int leftCount = 0;
        int rightCount = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == leftMajority) {
                leftCount++;
            }
            if (nums[i] == rightMajority) {
                rightCount++;
            }
        }
        return leftCount >= rightCount ? leftMajority : rightMajority;

    }
}

3、leetcode53：最大子序和

在这里插入图片描述

这题，是定长的子数组的话，那就是一个滑动窗口。现在不定长，可以这样想：如果前面一串的和小于0，那我再要他们和我加一起的话，只会让我越来越小，形象的说，过去那一串整体就是累赘，应该从我这儿重新开始累加。

反之，前面那一串的和大于0，那说明祖上有家产，不论多少，继承过来继续累加。前面那一串的和大于0，说明不管那一串有几个正数几个负数（几个挣钱的、几个败家的），传到我这儿总是有剩余钱的，没有负债，那就继承。

这题，不是区分哪一个元素是正数或负数，就来决定是丢是留，而是从一段上来看，是正的还是负的，比如：11，-10，999，不能一见到-10就把11也扔了，整体 > 0就可以累加

public class P53 {

    public static int maxSubArray(int[] nums) {
        if (null == nums || nums.length == 0) {
            return 0;
        }
        // 不能赋值0，否则，nums = {-1}时，有bug：和为-1，输出0
        int result = nums[0];
        int pre = 0;
        for (int num : nums) {
            // 如果过去前面那一串的和小于0，是累赘，那我就从自己这儿重新开始
            if (pre < 0) {
                pre = num;
            } else {
                // 如果过去前面那一串的和大于0，说明家里祖上有点家产，那就继承
                pre = pre + num;
            }
            // 每处理一个元素，覆盖下最值
            result = Math.max(result, pre);
        }
        return result;
    }
}