想做网站的公司好,排版设计素材,做网站对公司的作用,html5做网站链接一、小和问题
问题描述#xff0c;给定一个数组#xff0c;如[1, 3, 2, 6, 5]#xff0c;计算每个数左边小于自己的所有数的和#xff0c;并累加。例如#xff1a; 1左边没有数 3左边有一个小于自己的数 1 2左边有一个小于自己的数 1 6左边有三个小于自己的数 1 3 2 6…一、小和问题
问题描述给定一个数组如[1, 3, 2, 6, 5]计算每个数左边小于自己的所有数的和并累加。例如 1左边没有数 3左边有一个小于自己的数 1 2左边有一个小于自己的数 1 6左边有三个小于自己的数 1 3 2 6 5左边有三个小于自己的数 1 3 2 6 最后 1 1 6 6 14上面给定数组 [1, 3, 2, 6, 5] 的小和解就是 14. 解题思路这道题的常规思路是循环每个数然后再遍历它左边的所有数只要比自己小就累加到 sum 上。时间复杂度是 O(N^2)。
如何将它改写成 O(N^logN)复杂度的算法可以利用递归。
本题中我们要计算每个数左侧小于自己数的和反过来看就是每个数算一下右边有几个大于自己的数然后求和。还是以上面的数组为例 1右边有四个数大于自己4 * 1 4 3右边有两个数大于自己2 * 3 6 2右边有两个数大于自己2 * 2 4 6右边没有大于自己的数 5右边没有大于自己的数 最后 4 6 4 14和前一种按照题意原本的规则计算的结果完全一致。 有了这个逆向思路我们可以在归并排序 merge 的时候由于merge的左右两组一定是有序的在左组数较小并拷贝时计算右组中大于自己的数的个数乘以自身就就可以得到一个当前范围内右侧累计值 上图是一个常规的非对称情况的 merge 操作其中 1 3 已经通过merge排好序尽管已经是有序的但也会执行一次merge。
在merge的时候左组拷贝产生小和右组拷贝不产生小和。根据之前的逆向思路我们需要计算每个数右组比自己大的元素个数由于已经有了“左右两组各自有序”这个前提因此在copy左组元素的时候直接取右组当前比较的位置到 R 的元素个数即可而当左右两组当前比较的元素相等时我们必须先拷贝右组元素这是为了方便计算右组有几个数大于左组 实现及测试完整代码
/*** 小和问题*/
public class Code2_SmallSum {public static int smallSum(int[] arr) {if (arr null || arr.length 2)return 0;return process(arr, 0, arr.length - 1);}private static int process(int[] arr, int L, int R) {if (L R)return 0;int M L ((R - L) 1);int leftSum process(arr, L, M);int rightSum process(arr, M 1, R);int mergeSum merge(arr, L, M, R);return leftSum rightSum mergeSum;}private static int merge(int[] arr, int L, int M, int R) {int[] help new int[R - L 1];int p1 L;int p2 M 1;int i 0;int res 0;while (p1 M p2 R) {res arr[p1] arr[p2] ? (R - p2 1) * arr[p1] : 0;help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}while (p1 M) {help[i] arr[p1];}while (p2 R) {help[i] arr[p2];}for (i 0; i help.length; i) {arr[L i] help[i];}return res;}// for testpublic static int comparator(int[] arr) {if (arr null || arr.length 2) {return 0;}int res 0;for (int i 1; i arr.length; i) {for (int j 0; j i; j) {res arr[j] arr[i] ? arr[j] : 0;}}return res;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr new int[(int) ((maxSize 1) * Math.random())];for (int i 0; i arr.length; i) {arr[i] (int) ((maxValue 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr null) {return null;}int[] res new int[arr.length];for (int i 0; i arr.length; i) {res[i] arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 null arr2 ! null) || (arr1 ! null arr2 null)) {return false;}if (arr1 null arr2 null) {return true;}if (arr1.length ! arr2.length) {return false;}for (int i 0; i arr1.length; i) {if (arr1[i] ! arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr null) {return;}for (int i 0; i arr.length; i) {System.out.print(arr[i] );}System.out.println();}// for testpublic static void main(String[] args) {int testTime 500000;int maxSize 100;int maxValue 100;boolean succeed true;for (int i 0; i testTime; i) {int[] arr1 generateRandomArray(maxSize, maxValue);int[] arr2 copyArray(arr1);if (smallSum(arr1) ! comparator(arr2)) {succeed false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? Nice! : Fucking fucked!);}}二、逆序对个数问题
逆序对个数是经典考题也是常考题它的问题是这样的
给定一个数组如 [1, 3, 2, 6, 4] 在整个数组范围内只要两个数形成降序即判定为一个逆序对统计这个数组的逆序对个数 以上述数组为例3, 2 和 64都是逆序对因此该数组总共有两个逆序对。 题意非常好理解同时它也是上题小和问题的一个变种上面的小和问题通过逆向思维实际上计算的是右侧有几个比自己大的数然后累乘自身而本题是求右侧有多少个比自己小累加。
那么以升序排序的方式可以求右组比自己大的个数同理以降序排序的方式就可以求右组比自己小的个数。因此只需要降序merge并统计个数即可完整代码和测试如下
/*** 逆序对个数*/
public class Code2_ReversedPair {/*** 降序再count*/public static int reversedPairCount(int[] arr) {if (arr null || arr.length 2)return 0;return process(arr, 0, arr.length - 1);}private static int process(int[] arr, int L, int R) {if (L R)return 0;int M L ((R - L) 1);return process(arr, L, M) process(arr, M 1, R) merge(arr, L, M, R);}private static int merge(int[] arr, int L, int M, int R) {int[] help new int[R - L 1];int p1 L;int p2 M 1;int i 0;int count 0;while (p1 M p2 R) {count arr[p1] arr[p2] ? (R - p2 1) : 0;help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}while (p1 M) {help[i] arr[p1];}while (p2 R) {help[i] arr[p2];}for (i 0; i help.length; i) {arr[L i] help[i];}return count;}// for testpublic static int comparator(int[] arr) {int ans 0;for (int i 0; i arr.length; i) {for (int j i 1; j arr.length; j) {if (arr[i] arr[j]) {ans;}}}return ans;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr new int[(int) ((maxSize 1) * Math.random())];for (int i 0; i arr.length; i) {arr[i] (int) ((maxValue 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr null) {return null;}int[] res new int[arr.length];for (int i 0; i arr.length; i) {res[i] arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 null arr2 ! null) || (arr1 ! null arr2 null)) {return false;}if (arr1 null arr2 null) {return true;}if (arr1.length ! arr2.length) {return false;}for (int i 0; i arr1.length; i) {if (arr1[i] ! arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr null) {return;}for (int i 0; i arr.length; i) {System.out.print(arr[i] );}System.out.println();}// for testpublic static void main(String[] args) {int testTime 500000;int maxSize 100;int maxValue 100;System.out.println(测试开始);for (int i 0; i testTime; i) {int[] arr1 generateRandomArray(maxSize, maxValue);int[] arr2 copyArray(arr1);if (reversedPairCount(arr1) ! comparator(arr2)) {System.out.println(Oops!);printArray(arr1);printArray(arr2);break;}}System.out.println(测试结束);}
}三、两倍大问题
两倍大问题给定一个数组如[6, 7, 1, 3, 2]计算出每个数右侧比自身要小两倍还多的数的累计个数。
/*** 两倍大问题统计数组中每个比右边几个数两倍还大。* 6 7 1 3 2* 6比1、2 大两倍还多* 7比1、3、2大两倍还多* 因此总个数就是5个*/
public class Code4_BeggerTwice {public static int biggerTwice(int[] arr) {if (arr null || arr.length 2)return 0;int count process(arr, 0, arr.length - 1);return count;}private static int process(int[] arr, int L, int R) {if (L R)return 0;int M L ((R - L) 1);return process(arr, L, M) process(arr, M 1, R) merge(arr, L, M, R);}private static int merge(int[] arr, int L, int M, int R) {int[] help new int[R - L 1];int i 0;int p1 L;int p2 M 1;int count 0;// [M 1, R]int windowR M 1;for (int j L; j M; j) {while (windowR R arr[j] arr[windowR] * 2)windowR;count R - windowR 1;}while (p1 M p2 R) {help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}while (p1 M) {help[i] arr[p1];}while (p2 R) {help[i] arr[p2];}for (i 0; i help.length; i) {arr[L i] help[i];}return count;}// for testpublic static int comparator(int[] arr) {int ans 0;for (int i 0; i arr.length; i) {for (int j i 1; j arr.length; j) {if (arr[i] (arr[j] 1)) {ans;}}}System.out.println(arr2总数为 ans);return ans;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr new int[(int) ((maxSize 1) * Math.random())];for (int i 0; i arr.length; i) {arr[i] (int) ((maxValue 1) * Math.random()) - (int) ((maxValue 1) * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr null) {return null;}int[] res new int[arr.length];for (int i 0; i arr.length; i) {res[i] arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 null arr2 ! null) || (arr1 ! null arr2 null)) {return false;}if (arr1 null arr2 null) {return true;}if (arr1.length ! arr2.length) {return false;}for (int i 0; i arr1.length; i) {if (arr1[i] ! arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr null) {return;}for (int i 0; i arr.length; i) {System.out.print(arr[i] );}System.out.println();}// for testpublic static void main(String[] args) {int testTime 500000;int maxSize 10;int maxValue 10;System.out.println(测试开始);for (int i 0; i testTime; i) {int[] arr1 generateRandomArray(maxSize, maxValue);
// System.out.println(原始数组);
// printArray(arr1);int[] arr2 copyArray(arr1);if (biggerTwice(arr1) ! comparator(arr2)) {System.out.println(Oops!);printArray(arr1);printArray(arr2);break;}}System.out.println(测试结束);}}四、求区间和子数组个数
本题是LeetCode真题——327题区间和个数https://leetcode-cn.com/problems/count-of-range-sum/
提议描述给定一个数组 arr两个整数 lower 和 upper计算出 arr 中有多少个子数组的累加和在 [lower, upper] 范围上要求子数组必须连续。
例如[1, 3, -2] 求累加和范围在 [2, 4] 范围上的子数组个数 [1] 不符合 [1, 3] 符合 [1, 3, -2] 符合 [3] 符合 [3, -2] 不符合 [-2] 不符合 所以符合达标的子数组分别是[1, 3]、[1, 3, -2]、[3] 共 3 个子数组。 小提示枚举子数组的方式有两种一种是以头位置开始上面就是这种方式还有一种是以尾为标准例如 以 0 位置结尾的子数组[1] 以 1 位置结尾的子数组[1, 3]、[3]、 以 2 位置结尾的子数组[1,3,-2]、[3, -2]、[-2] 解题思路这是一道困难难度的面试题。在解答本题之前需要有一些转换技巧作为铺垫——前缀和问题。
前缀和问题的描述是一个数组 arr[] 元素是无序整数正负0都有给定一个 [i, j] 范围求累加和。这个问题可以算得上是区间和问题的一个重要逻辑单元。
最傻瓜式的方式无非就是从 i 到 j 遍历元素然后累加。如何优化可以转变成“前缀和问题”。
求[0, j] 累加和减去[0i - 1] 范围的累加和即可得到 [i, j] 范围的累加和。我们称之为“前缀和”就是因为每个位置的前缀和都是从0位置开始一直加到自身位置而每个位置上的前缀和只需要遍历一遍就可以轻松得出。
如果我们实现通过一次遍历得到了和原数组每个位置元素对应的前缀和那么 [i, j] 累加和问题就可以轻松变为从前缀和数组中取 j 和 i 位置上的两个数然后相减抛去只执行一次的前缀和数组的生成后面的每次操作都是常数时间复杂度极大地提升了效率。 public static int rangeSum(int[] arr, int lower, int upper) {if (arr null || lower 0 || upper arr.length)throw new IllegalArgumentException(参数不合法);int[] preSum new int[arr.length];preSum[0] arr[0];for (int i 1; i arr.length; i) {preSum[i] preSum[i - 1] arr[i];}return preSum[upper] - preSum[lower - 1];}
有了以上这些知识的铺垫再来回看原题求累加和属于 [lower, upper] 范围的子数组个数如果有了原数组对应的前缀和数组假设以 i 位置为例求以 i 位置结尾的子数组累加和属于 [lower, upper] 范围对应前缀和数组就是求以 i 位置结尾的前缀和与多少个左侧前缀和相减的差属于[lower, upper] 如果 i 位置上的前缀和为 x那么这个 i 位置左侧的小前缀和的区间范围就应该落在与其互补的 [x - upper, x - lower] 范围上简言之就是求前缀和数组上i 位置左侧有多少个元素属于 [x-upper, x - lower] 范围由于我们一定可以通过以各个位置上的数结尾的子数组穷举全部子数组因此利用归并求出每个 i 位置左侧达标的元素并计数最终就一定会统计出全部达标的子数组个数。 上图中移位换项指的是 i - j [lower, upper] 将 j 移到一侧得出 j [i - lower, i - upper] 。
完整代码如下
public class Code1_CountOfRangeSum {public static int countRangeSum(int[] arr, int lower, int upper) {if (arr null || arr.length 0)throw new IllegalArgumentException(参数非法);long[] preSum new long[arr.length];preSum[0] arr[0];for (int i 1; i arr.length; i) {preSum[i] preSum[i - 1] arr[i];}return process(preSum, 0, preSum.length - 1, lower, upper);}private static int process(long[] preSum, int L, int R, int lower, int upper) {if (L R)return preSum[L] lower preSum[L] upper ? 1 : 0;int M L ((R - L) 1);return process(preSum, L, M, lower, upper) process(preSum, M 1, R, lower, upper) merge(preSum, L, M, R, lower, upper);}private static int merge(long[] preSum, int L, int M, int R, int lower, int upper) {int count 0;int windowL L;int windowR L;// [windowL, windowR)for (int i M 1; i R; i) {long min preSum[i] - upper;long max preSum[i] - lower;while (windowR M preSum[windowR] max)windowR;while (windowL M preSum[windowL] min)windowL;count windowR - windowL;}long[] help new long[R - L 1];int i 0;int p1 L;int p2 M 1;while (p1 M p2 R) {help[i] preSum[p1] preSum[p2] ? preSum[p1] : preSum[p2];}while (p1 M)help[i] preSum[p1];while (p2 R)help[i] preSum[p2];for (i 0; i help.length; i) {preSum[L i] help[i];}return count;}
}
