做低价的跨境电商网站,wordpress 分享本文,手机号网站源码,wordpress慢的原因题目 假设一个固定大小为W的窗口#xff0c;依次划过arr#xff0c; 返回每一次滑出状况的最大值 例如#xff0c;arr [4,3,5,4,3,3,6,7], W 3 返回#xff1a;[5,5,5,4,6,7]
暴力对数器 暴力对数器方法主要是用来做校验#xff0c;不在乎时间复杂度#xff0c;逻辑上…题目 假设一个固定大小为W的窗口依次划过arr 返回每一次滑出状况的最大值 例如arr [4,3,5,4,3,3,6,7], W 3 返回[5,5,5,4,6,7]
暴力对数器 暴力对数器方法主要是用来做校验不在乎时间复杂度逻辑上能对即可测试方法时采用大数据量和算法作对比看是否有报错。 举例此时数组arr {3157658} w 3。 从头开始遍历当来到第一组315刚好凑齐w个数时此时取Max最大值为5。 继续向下此时3过期来到157取Max最大值为7。 再次向后取值1位置过期来到了576取Max最大值为7。 765最大值为7 658最大值为8所以最终答案为{57778}。 代码 L从开始R从w-1开始 LR直到R到arr.length停止遍历每次遍历都取L的最大值。将max赋值给result数组。 public static int[] right(int[] arr, int w) {if (arr null || w 1 || arr.length w) {return null;}int index 0;int L 0;int R w - 1;int N arr.length;int[] result new int[arr.length - w 1];while (R N) {int max arr[L];for (int i L 1; i R; i) {max Math.max(max, arr[i]);}result[index] max;L;R;}return result;}滑动窗口 滑动窗口方法用LinkList来实现双端队列结构不用过多考虑w个数严格按照头 —— 尾是从大到小的顺序即可。 变量R从0开始向arr.length遍历。 如果队列中不为null并且新加入的元素大于等于队列尾端元素就将满足条件的尾端元素全部弹出。而后将该元素加入到双端队列尾部。 当第一次R的下标来到了w - 1位置证明已经遍历过了w个数将此时队列头部最大值填充到新数组中。 如果当前头部最大值 等于 R - w 证明此时头部的值已经过期了要剔除掉。
代码 public static int[] getMaxWindow(int[] arr, int w) {if (arr null || w 1 || arr.length w) {return null;}LinkedListInteger qmax new LinkedList();int[] result new int[arr.length - w 1];int index 0;for (int R 0; R arr.length; R) {// 如果qmax双端队列不为null//并且尾端元素小于等于当前元素while (!qmax.isEmpty() arr[qmax.peekLast()] arr[R]) {//满足条件的所有尾端元素全部弹出qmax.pollLast();}//将当前元素假如到队尾qmax.addLast(R);//R - w如果等于当前头部最大值//下一次循环R 头部最大值要过期了弹出if (R - w qmax.peekFirst()) {qmax.pollFirst();}// R w - 1R从0开始假设w 3则 w - 1 2说明此时窗口已经划过三个元素该出现一个当前窗口最大值了if (R w - 1) {result[index] arr[qmax.peekFirst()];}}return result;}测试 采用随机生成数组的方式大样本量对两个方法进行测试。 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 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;}public static void main(String[] args) {int maxValue 100;int maxLength 100;int testNum 100000;for (int i 0; i testNum; i) {int[] arr generateRandomArray(maxLength, maxValue);int w (int) (Math.random() * (arr.length 1));int[] ans1 getMaxWindow(arr, w);int[] ans2 right(arr, w);if (!isEqual(ans1, ans2)) {System.out.println(w : w);for (int num : arr) {System.out.print(num );break;}}}}
