乐趣区

关于算法-数据结构:归并排序干掉的LeetCode第一个Hard题LeetCode327-区间和的个数帅

大家好,我是周一。

最近几篇算法,咱们都是聊的归并排序,明天再开一篇。再聊两题。

一、大于右侧数的两倍

怕大家忘了归并排序,所以先拿一题练练手。

1、题目形容

求给定数组中,以后数 大于 右侧数两倍 的个数

2、例子

数组:[6, 7, 3, 2, 1]

以后数大于右侧数的两倍的数有(6,2),(6,1),(7,3),(7,2),(7,1),(3,1)

所有总共有 6 个。

3、思路

认真看过归并排序:解决小和、逆序对问题的搭档都晓得,咱们在求解时,都是和 merge 操作放在一起的。然而此题再和 merge 操作放在一起求解,难度、代码复杂度就很大了。

所以,咱们换个角度,很简略,咱们把 求个数的操作 和 merge 操作 分成两个循环独自求,霎时就恍然大悟了。

4、具体的参考代码

只有 merge 操作的代码,其余和归并排序的截然不同

private static int merge(int[] arr, int l, int mid, int r) {
        int num = 0;
        // l...mid, mid+1...r, 目前右组寻找的范畴 [mid+1, windowR)
        int windowR = mid + 1;
        for (int i = l; i <= mid; i++) {while (windowR <= r && arr[i] > (arr[windowR] << 1)) {windowR++;}
            // 此时,符合条件的个数为 (windowR - (mid+1))
            // 因为此时 windowR 不满足要求,所以不是(windowR - (mid+1)) +1
            num += windowR - mid - 1;
        }

        int[] help = new int[r - l + 1];
        int i = 0;
        int pL = l;
        int pR = mid + 1;
        while (pL <= mid && pR <= r) {
            // 谁小拷贝谁(相等的拷贝左组的)help[i++] = arr[pL] <= arr[pR] ? arr[pL++] : arr[pR++];
        }
        while (pL <= mid) {help[i++] = arr[pL++];
        }
        while (pR <= r) {help[i++] = arr[pR++];
        }
        for (int j = 0; j < help.length; j++) {arr[l + j] = help[j];
        }

        return num;
    }

OK,热身结束。明天的重头戏当然是如何用归并排序解决 LeetCode 的这道 Hard 题

二、LeetCode327. 区间和的个数

那么咱们就看看在 LeetCode 的题目中,归并排序有何妙用呢。

1、题目形容

https://leetcode-cn.com/probl…

给你一个整数数组 nums 以及两个整数 lower 和 upper。求数组中,值位于范畴 [lower, upper](蕴含 lower 和 upper)之内的 区间和的个数。

区间和 S(i, j) 示意在 nums 中,地位从 i 到 j 的元素之和,蕴含 i 和 j (i ≤ j)。

2、例子

输出:nums = [-2,5,-1], lower = -2, upper = 2

输入:3

解释:存在三个区间:[0,0]、[2,2] 和 [0,2],对应的区间和别离是:-2、-1、2。

3、思路

首先,咱们要先晓得,前缀和的概念。

前缀和 :preSum[j] 所示意的 j 地位的前缀和含意是,原数组 0 到 j 地位的数的和。

为啥要用前缀和。因为对于频繁求数组某个范畴内数的和时,应用前缀和代替这样在求原数组 i – j 范畴内数的和,则等于前缀和数组中 preSum[j] – preSum[i – 1]。这样就不必每次求和时都遍历数组了。

外围思路如下

1. 应用前缀和代替原数组;

2. 在归并排序合并办法内,统计满足条件的累加和个数 和 合并操作离开。

3. 每次合并操作,对于右组(前缀和数组)中的每一个数 X[i],求左组(前缀和数组)所有数中有多少个范畴在 [X[ i] – upper, X[i] – lower]上,将满足条件的个数累加起来即为最初的后果

可能看的云里雾里,来,咱们看看具体的代码

4、具体的参考代码

/**
 * 形容:https://leetcode.com/problems/count-of-range-sum/。* 中文版:(327. 区间和的个数)https://leetcode-cn.com/problems/count-of-range-sum/
 * <p>
 * 给你一个整数数组 nums 以及两个整数 lower 和 upper。* 求数组中,值位于范畴 [lower, upper](蕴含 lower 和 upper)之内的 区间和的个数。* <p>
 * 区间和 S(i, j) 示意在 nums 中,地位从 i 到 j 的元素之和,蕴含 i 和 j (i ≤ j)。* <p>
 * 后果间接在 leetcode 测试
 * <p> 
 *
 * @author Java 和算法学习:周一
 */
public class CountOfRangeSum {public static int countRangeSum(int[] nums, int lower, int upper) {if (nums == null || nums.length < 1) {return 0;}

        // 求原数组的前缀和
        long[] preSum = new long[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {preSum[i] = preSum[i - 1] + nums[i];
        }

        return process(preSum, 0, preSum.length - 1, lower, upper);
    }

    private static int process(long[] preSum, int L, int R, int lower, int upper) {// L == R 时,preSum[L] 示意原数组 [0, L]范畴上的累加和
        // 在 merge 过程中,会疏忽掉左组一个数也没有的这种状况,所以在这里补充这种状况
        if (L == R) {return preSum[L] >= lower && preSum[L] <= upper ? 1 : 0;
        }
        int mid = L + ((R - L) >> 1);
        // 返回左组和右组在合并过程中产生的满足条件的累加和个数
        return process(preSum, L, mid, lower, upper)
                + process(preSum, mid + 1, R, lower, upper)
                + merge(preSum, L, mid, R, lower, upper);
    }

    private static int merge(long[] arr, int L, int mid, int R, int lower, int upper) {
        // 累加和个数
        int ans = 0;
        // 左组寻找的左侧地位(必定是从以后的 L 地位开始)int windowL = L;
        // 左组寻找的右侧地位(必定也是从以后的 L 地位开始)int windowR = L;
        // 对于右组的每一个数 X,在左组中寻找值在 [X-upper, X-lower] 之间的个数
        for (int i = mid + 1; i <= R; i++) {long min = arr[i] - upper;
            long max = arr[i] - lower;

            // 因为是在左组中寻找,所以下标不能超过 mid
            // 寻找以后值比 max 大的第一个地位(因为等于 max 的时候右移了一位,所以不蕴含此地位)while (windowR <= mid && arr[windowR] <= max) {windowR++;}

            // 寻找以后值大于等于 min 的第一个地位(因为等于 min 的时候没有右移,所以蕴含此地位)while (windowL <= mid && arr[windowL] < min) {windowL++;}

            // 最初满足要求的累加和个数为 [windowL, windowR),即 windowR - windowL,windowR 是开区间,所以不 +1
            ans += windowR - windowL;
        }

        // 以下是经典的 merge 过程
        long[] help = new long[R - L + 1];
        int i = 0;
        int pL = L;
        int pR = mid + 1;
        while (pL <= mid && pR <= R) {help[i++] = arr[pL] <= arr[pR] ? arr[pL++] : arr[pR++];
        }
        while (pL <= mid) {help[i++] = arr[pL++];
        }
        while (pR <= R) {help[i++] = arr[pR++];
        }
        for (int j = 0; j < help.length; j++) {arr[L + j] = help[j];
        }

        return ans;
    }

}

LeetCode 测试后果:

只管执行用时略微差了那么点点,但毕竟是通过的第一道 Hard 题,一步一步来,置信本人

退出移动版