网站制作专业的公司哪家好,深圳龙华区邮政编码,国外网站推广公司,亚马逊aws永久免费服务器递归
例子引出
使用递归的方法求出数组中的最大值#xff08;利用的是栈#xff09;求中点的方法改进
mid (left right) / 2 //但是如果left和right的数很大#xff0c;相加会造成内容溢出
改进为 mid left (right - left) / 2 //(right - left)得到整个的长度…递归
例子引出
使用递归的方法求出数组中的最大值利用的是栈求中点的方法改进
mid (left right) / 2 //但是如果left和right的数很大相加会造成内容溢出
改进为 mid left (right - left) / 2 //(right - left)得到整个的长度除以2之后再加上左边的点就可以得到中点的位置
改进为 mid left (right - left) 1 //使用位运算加快计算速度
代码
package com.example.demo.class01;public class Code08_GetMax {public static void main(String[] args) {int arr[] {1,2,4,3,2,8,6};int c 0;c getMax(arr);System.out.println(c);}public static int getMax(int[] arr){if(arr null || arr.length 0){System.out.println(输入数组不合理);}return process(arr,0,arr.length - 1);}public static int process(int[] arr,int L,int R){if(L R){return arr[L];} //arr[L..R]只有一个数的时候直接返回base caseint mid L ((R - L)1);int leftMax process(arr,L,mid);int rightMax process(arr,mid1,R);return Math.max(leftMax,rightMax);}
}
//8
master公示的使用
用于分析递归用于解决 子问题规模 是一致的问题
T(N) a*T(N/b) O(N^d)1,log(b,a) d - 复杂度为O(N^log(b,a))
2,log(b,a) d - 复杂度为O(N^d * logN)
3,log(b,a) d - 复杂度为O(N^d)
归并排序
整体就是一个简单排序左边排好顺序右边排好顺序使整体有序时间复杂度是O(N*logN)额外复杂度是O(N) 代码
package com.example.demo.class01;import java.util.Arrays;public class MergeSort {public static void mergeSort(int[] arr) {if (arr null || arr.length 2) {return;}process(arr, 0, arr.length - 1);}public static void process(int[] arr, int L, int R) {if (L R) {return;}int mid L ((R - L) 1);process(arr, L, mid);process(arr, mid 1, R);merge(arr, L, mid, R);}public static void 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;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];}}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// 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);mergeSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? Nice! : Fucking fucked!);int[] arr generateRandomArray(maxSize, maxValue);printArray(arr);mergeSort(arr);printArray(arr);}}小和问题
定义在一个数组中每一个数比前数小的数进行累加叫做这个数的小和。转化为 右边大于我的个数 * 我本身大小 累加和这个数值和小和得到的数据一致 res arr[p1] arr[p2] ? (r - p2 1) * arr[p1] : 0;p1指向左边的数p2指向右边的数r是右边部分最右边的边界。r-p2 1 得到比当前左边元素大的个数 再乘以当前元素本身将所有元素按照上述流程进行最后就得到了小和 例子【13425】1左边比1小的数无3左边比3小的数14左边比4小的数132左边比2小的数15左边比5小的数1342累加求和16
使用归并排序解决小和问题
归并排序遇到相同的元素先移动左侧是为了保证程序的稳定性而这里先移动右侧的元素是为了确定比左侧指针指向的元素大的右侧区块中的元素的个数小和问题出现在三个地方左侧区块内排序右侧区块内排序左右侧区块合并
代码
package class02;public class Code02_SmallSum {public static int smallSum(int[] arr) {if (arr null || arr.length 2) {return 0;}return process(arr, 0, arr.length - 1);}// arr[L..R]既要排好序也要求小和public static int process(int[] arr, int l, int r) {if (l r) {return 0;}int mid l ((r - l) 1);return process(arr, l, mid) process(arr, mid 1, r) merge(arr, l, mid, r);}public 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 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!);}}类似于逆序对问题如果左边的数比右边的数大则二者构成一个逆序对原理类似 res arr[p1] arr[p2] ? (m - p1 1) : 0;荷兰国旗问题
快速排序 给定数组arr和数num将小于等于num的数放在数组的左边大于num的数放在数组的右边要求时间复杂度为O(N),空间复杂度为O(1);不要求内部有序将数组分为三个部分以num为界限分为小于等于区、大于区和待定区。指针指向数组的第一个元素判定指针指向的元素是否小于等于num如果成立当前数和小于等于区的下一个数交换然后小于等于区向右移动指针也向右移动如果指针指向的元素大于num那么指针直接跳过该元素向右移动。
package class02;public class Code05_NetherlandsFlag {public static int[] partition(int[] arr, int l, int r, int p) {int less l - 1;int more r 1;while (l more) {if (arr[l] p) {swap(arr, less, l);} else if (arr[l] p) {swap(arr, --more, l);} else {l;}}return new int[] { less 1, more - 1 };}// for testpublic static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}// for testpublic static int[] generateArray() {int[] arr new int[10];for (int i 0; i arr.length; i) {arr[i] (int) (Math.random() * 3);}return arr;}// 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();}public static void main(String[] args) {int[] test generateArray();printArray(test);int[] res partition(test, 0, test.length - 1, 1);printArray(test);System.out.println(res[0]);System.out.println(res[1]);}
}第二个问题
荷兰国旗问题给定数组arr和数num将小于等于num的数放在数组的左边等于num的数放在数组的中间大于num的数放在数组的右边要求时间复杂度为O(N),空间复杂度为O(1)将数组分为三个部分小于区、中间区和大于区。首先用指针指向数组的第一个元素如果当前指向的数小于num则小于区下一个元素和当前数值侧面交换小于区域向右边扩指针向右边移动如果当前指针指向的元素和num相等那么指针直接跳过移动到下一个位置如果当前指针指向的元素大于num那么大于区的前一个元素和当前指针指向的元素交换大于区域向左边扩展但是当前指针不可以移动位置因为交换了元素不知道这个交换元素和num的大小
package class02;import java.util.Arrays;public class Code06_QuickSort {public static void quickSort(int[] arr) {if (arr null || arr.length 2) {return;}quickSort(arr, 0, arr.length - 1);}public static void quickSort(int[] arr, int l, int r) {if (l r) {swap(arr, l (int) (Math.random() * (r - l 1)), r);int[] p partition(arr, l, r);quickSort(arr, l, p[0] - 1);quickSort(arr, p[1] 1, r);}}public static int[] partition(int[] arr, int l, int r) {int less l - 1;int more r;while (l more) {if (arr[l] arr[r]) {swap(arr, less, l);} else if (arr[l] arr[r]) {swap(arr, --more, l);} else {l;}}swap(arr, more, r);return new int[] { less 1, more };}public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {//l到r随机选一个数做等概率划分 最差情况发生概率下降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);quickSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? Nice! : Fucking fucked!);int[] arr generateRandomArray(maxSize, maxValue);printArray(arr);quickSort(arr);printArray(arr);}}快排的时间复杂度是 o(N*logN)
