归并排序干掉的LeetCode第一个Hard题(LeetCode327|归并排序干掉的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/
* * 给你一个整数数组 nums 以及两个整数 lower 和 upper 。
* 求数组中,值位于范围 [lower, upper] (包含 lower 和 upper)之内的 区间和的个数 。
* * 区间和 S(i, j) 表示在 nums 中,位置从 i 到 j 的元素之和,包含 i 和 j (i ≤ j)。
* * 结果直接在leetcode测试
*
*
* @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测试结果:
文章图片
【归并排序干掉的LeetCode第一个Hard题(LeetCode327|归并排序干掉的LeetCode第一个Hard题(LeetCode327 区间和的个数),帅】尽管执行用时稍微差了那么点点,但毕竟是通过的第一道Hard题,一步一步来,相信自己。
推荐阅读
- 一个选择排序算法
- 排序(归并排序)
- 【图解】9张图彻底搞懂堆排序
- vue|vue 上移 下移 删除 排序
- 必须掌握的八种基本排序算法
- 【排序】插入排序算法
- 信浓号,被板砖干掉的黑帮老大
- 排序之冒泡和选择
- 2019-03-02|2019-03-02 排序
- Java数据结构与算法(十)排序算法01