做ppt的兼职网站,wordpress 弹出视频,广州公司宣传片,在线免费logo设计生成器题目 给定一个整型数组arr#xff0c;和一个整数num 某个arr中的子数组sub#xff0c;如果想达标#xff0c;必须满足#xff1a; sub中最大值 – sub中最小值 num#xff0c; 返回arr中达标子数组的数量
暴力对数器 暴力对数器方法主要是用来和另一个方法互相校验正…题目 给定一个整型数组arr和一个整数num 某个arr中的子数组sub如果想达标必须满足 sub中最大值 – sub中最小值 num 返回arr中达标子数组的数量
暴力对数器 暴力对数器方法主要是用来和另一个方法互相校验正确性所以不用考虑时间复杂度。 因为要求的是子数组中的最大值和子数组中的最小值相减 num。所以整体思路是这样 求数组 0 ~ N - 1范围内所有子数组找到子数组中最小值看相减后是否达标如果达标则count进行计数。最后return count。 所有子数组挨个枚举就是 0~ 0范围内子数组0 ~ 1范围内子数组 0 ~ N - 1范围内子数组。 1 ~ 1范围内子数组1 ~ 2 范围内子数组 1 ~ N - 1范围内子数组…。 每个范围内子数组进行枚举需要两层for循环找到每个子数组范围内的最大值和最小值额外需要1层for循环所以时间复杂度是 O N 3 ON^3 ON3。
代码 public static int right(int[] arr, int sum) {if (arr null || arr.length 0 || sum 0) {return 0;}int N arr.length;int count 0;for (int L 0; L N; L) {for (int R L; R N; R) {int max arr[L];int min arr[L];for (int i L 1; i R; i) {min Math.min(min, arr[i]);max Math.max(max, arr[i]);}if (max - min sum) {count;}}}return count;}滑动窗口算法 采用滑动窗口算法的时间复杂度是 O N ON ON因为窗口不可回退所以只需要一次遍历即可找出所有符合条件的子数组。 这道题中需要2个窗口一个维护L…R范围内的最大值一个维护L…R范围内的最小值。而在看代码之前需要达成这样的2个共识
如果L…R范围内 max - min num那么L…R范围内所有子数组都满足 max - min num都会达标。如果L…R范围内 max - min num那么无论R继续向右扩窗口或者L继续向左阔窗口那L…R范围内子数组依然不达标。
解释1 因为max - min num所以L…R 范围内剩余子数组相减子数组范围内的两个数一定是 max min的最大值变小了最小值变大了所以一定会 num。 解释2 因为max - min num根据滑动窗口的特性在维护L…R范围内最大值的双端队列中后进来的数一定是当前双端队列中的值才会进行替换在维护L…R范围内最小值的双端队列中后进来的数一定是当前双端队列中的值才会进行替换。 所以无论向右或者向左范围内子数组一定依然不达标。
达成这两个共识之后代码就简单了很多在维护双端队列特性的同时如果满足 max - min num则R向右移直到不满足 max - min num为止。碰见一次不满足则计算一次当前子数组的个数直到循环完成。
代码
public static int num(int[] arr, int sum) {if (arr null || arr.length 0 || sum 0) {return 0;}LinkedListInteger minWindow new LinkedList();LinkedListInteger maxWindow new LinkedList();int R 0;int count 0;int N arr.length;for (int L 0; L N; L) {while (R N) {//如果max双端队列不为null并且队列尾端值当前值则弹出while (!maxWindow.isEmpty() arr[maxWindow.peekLast()] arr[R]) {maxWindow.pollLast();}maxWindow.addLast(R);//如果min双端队列不为null并且队列尾端值当前值则弹出while (!minWindow.isEmpty() arr[minWindow.peekLast()] arr[R]) {minWindow.pollLast();}minWindow.addLast(R);//如果满足条件则R一直 直到不满足条件为止if (arr[maxWindow.peekFirst()] - arr[minWindow.peekFirst()] sum) {R;} else {break;}}//看R - L范围内共有多少个子数组count R - L;//因为这两个判断走完L就要进行//所以需要判断当前双端队列中头部值是否要过期了if (maxWindow.peekFirst() L) {maxWindow.pollFirst();}if (minWindow.peekFirst() L) {minWindow.pollFirst();}}return count;}测试 随机生成数组和sum采用大数据样本量进行测试用上面两个方法来相互验证。
public static int[] generateRandomArray(int maxLength, int maxValue) {int[] arr new int[(int) ((maxLength 1) * Math.random())];for (int i 0; i arr.length; i) {arr[i] (int) ((maxValue 1) * Math.random());}return arr;}public static void main(String[] args) {int maxLength 40;int maxValue 10000;int sum 10000;int testNum 1000000;System.out.println(测试开始);for (int i 0; i testNum; i) {int[] arr generateRandomArray(maxLength, maxValue);sum (int) ((sum 1) * Math.random());int ans1 right(arr, sum);int ans2 num(arr, sum);if (ans1 ! ans2) {for (int num : arr) {System.out.print(num );}System.out.println();System.out.println(sum : sum);System.out.println(ans1 : ans1);System.out.println(ans2 : ans2);System.out.println(Oops!!);break;}}System.out.println(测试结束);}
