数据库网站开发,站长之家特效网站,网推推荐信,百度收录官网学习视频#xff1a;一周刷爆LeetCode#xff0c;算法大神左神#xff08;左程云#xff09;耗时100天打造算法与数据结构基础到高级全家桶教程#xff0c;直击BTAJ等一线大厂必问算法面试题真题详解#xff08;马士兵#xff09;_哔哩哔哩_bilibili
时间复杂度
一个操…学习视频一周刷爆LeetCode算法大神左神左程云耗时100天打造算法与数据结构基础到高级全家桶教程直击BTAJ等一线大厂必问算法面试题真题详解马士兵_哔哩哔哩_bilibili
时间复杂度
一个操作如果和样本的数据量没有关系每次都是固定时间内完成的操作叫做常数操作。
时间复杂度为一个算法流程中常数操作数量的一个指标。常用O读作big O来表示。具体来说先要对一个算法流程非常熟悉然后去写出这个算法流程中发生了多少常数操作进而总结出常数操作数量的表达式。
在表达式中只要高阶项不要低阶项也不要高阶项的系数剩下的部分如果为f(N)那么时间复杂度就位O(f(N))。
评价一个算法流程的好坏先看时间复杂度的指标然后再分析不同数据样本下的实际运行时间也就是“常数项时间”.
常数操作例如数组根据索引寻值加、减、乘、除、比较
排序
选择排序
每次选择 i 到 n-1 范围内值最小的索引位置 t 每一次内层循环结束之后交换 i 和 t 索引位置上的值每一次外层循环 i 的值加 1
private static void selectSort(Integer[] nums) {for(int i0;inums.length-1;i){int ti;for(int ji1;jnums.length;j){if(nums[t]nums[j]){tj;}}swap(nums,i,t);}}
时间复杂度O(n^2) 空间复杂度O(1)
冒泡排序
每次从 0 到 i 的范围中将相邻的值进行两两比较将大的一个值移到后面这样每一次内层循环结束后i 位置的值就是0 到 i 范围内最大的值每一次外层循环 i 的值减 1.
private static void BubbleSort(Integer[] nums) {int nnums.length;for(int in-1;i0;i--){for(int j0;ji;j){if(nums[j]nums[j1]){swap(nums, j, j1);}}}}
时间复杂度O(n^2) 空间复杂度O(1) 插入排序
i 从 0 开始维护一个 0 到 i 范围的有序数组每一次 i 令 j 等于 ij 所在位置的元素 和 j-1 所在位置的元素进行比较 因为前 j-1 个元素是有序的所以 j 就往前进行比较如果 j 所在位置 比 j-1 小,就进行交换再往前进行比较知道比前面的大为止。
private static void MySort(Integer[] nums) {if(numsnull || nums.length2){return;}int lnums.length;for(int i1;il;i){for(int ji;j0;j--){if(nums[j]nums[j-1]){swap(nums,j,j-1);}else{break;}}}}
最坏情况下 时间复杂度为 O(n^2)空间复杂度为O(1)
归并排序
将一个数组分为左右两个子数组先将这两个子数组分别排好序再融合使得父数组也有序。
public static void mergeSort(int[] arr,int l,int r){if(lr) return;process(arr,l,r);}
private static void process(int[] arr, int l, int r) {if(lr) return;int midl((r-l)1);process(arr,l,mid);process(arr,mid1,r);merge(arr,l,mid,r);}
private static void merge(int[] arr, int l, int m, int r) {int[] helpnew int[r-l1];int p1l;int p2m1;int i0;while(p1m p2r){help[i]arr[p1]arr[p2]?arr[p1]:arr[p2];}while(p1m){help[i]arr[p1];}while (p2r){help[i]arr[p2];}for (int j 0; j help.length; j) {arr[lj]help[j];}}
根据master公式可以得到
T(N) 2T(N/2)O(N) -- 每一次将父函数分成两个数据量为父函数一半的子函数mergn函数的时间复杂度为O(N)
所以log(a,b)d--log(2,2)1
所以归并排序的时间复杂度为O(N*logN)空间复杂度O(N)
归并排序的扩展
1小和问题
在一个数组中每一个数左边比当前数小的数累加起来叫做这个数组的小和。求一个数组的小和
例如[1,3,4,2,5]左边比1小的数没有为03左边比3小的数1个14左边比4小的数1 * 11 * 342左边比2小的数1个15左边比5小的数134210所以小和为01411016。
也可以看一个数右边有几个比他大的数1右边有4个数比他大1 * 443右边有两个数比他大2 * 364右边有1个数比他大1 * 442右边有1个数比他大1 * 225右边没有比他大的数 0所以小和为4642016。
代码实现
public static int smallSum(int[] arr,int l,int r){if(lr) return 0;return process(arr,l,r);}
private static int process(int[] arr, int l, int r) {if(lr) return 0;int midl((r-l)1);return process(arr,l,mid) process(arr,mid1,r) merge(arr,l,mid,r);}
private static int merge(int[] arr, int l, int m, int r) {int[] helpnew int[r-l1];int p1l;int p2m1;int i0;int res0;while(p1m p2r){//判断右边数组中有几个比左边数组当前p1下标下的数大计算和resarr[p1]arr[p2]?(r-p21)*arr[p1]:0;//在merge的时候当右边数组p2下标对应的数跟左边数组p1下标对应的数相等的时候先把右边数组的数加入到临时数组中因为在去掉了右边与左边相等的数之后才能得到右边比左边大的数的数量。help[i]arr[p1]arr[p2]?arr[p1]:arr[p2];}while(p1m){help[i]arr[p1];}while (p2r){help[i]arr[p2];}for (int j 0; j help.length; j) {arr[lj]help[j];}return res;}
流程图 2逆序对问题
在一个数组中左边的数如果比右边的数大则拆两个数构成一个逆序对请打印所有逆序对。
代码
//int[] arr{3,2,4,5,1};
private static int merge(int[] arr, int l, int m, int r) {int[] helpnew int[r-l1];int p1l;int p2m1;int i0;int res0;while(p1m p2r){//在 1的代码上加入这一段判断逻辑就可以打印出所有的逆序对if(arr[p1]arr[p2]){int p11p1;while(p11m){System.out.println([arr[p11] arr[p2]]);}}resarr[p1]arr[p2]?(r-p21)*arr[p1]:0;//这里与 1有差别当左边和右边相等的时候移动左边的help[i]arr[p1]arr[p2]?arr[p1]:arr[p2];}while(p1m){help[i]arr[p1];}while (p2r){help[i]arr[p2];}for (int j 0; j help.length; j) {arr[lj]help[j];}return res;}
运行结果
[3 2]
[5 1]
[2 1]
[3 1]
[4 1] 快速排序
思考问题
1给定一个数组arr和一个数num请把小于等于num的数放在数组的左边大于num的数放在数组右边。要求额外空间复杂度为O(1)时间复杂度为O(N)。
思路定义一个小于等于区初始下标为-1i 从0开始遍历数组可以分为两种情况 1arr[i] numnums[i]和小于等于区的下一个数交换小于区右扩i。2arr[i] numi。
代码
//arr{3,4,6,7,5,3,5,8},num5
public static void func1(int[] arr,int num){int i0;int left-1;while(iarr.length){if(arr[i]num){swap(arr,left,i);}else if(arr[i]num){i;}}System.out.println(Arrays.toString(arr));}
运行结果
[0, 0, 5, 3, 5, 7, 6, 8] 2荷兰国旗问题给定一个数组arr和一个数num请把小于num的数放在数组的左边。等于num的数放在数组的中间大于num的数放在数组的右边要求额外空间复杂度为O(1)时间复杂度O(N)。
思路定义一个小于区初始下标为-1定义一个大于区初始下标为arr.lengthi 从0开始遍历数组有三种情况1arr[i] num nums[i]和小于区的下一个数交换小于区右扩i。2arr[i] num i。3arr[i] num 交换 num[i] 和大于区前一个数大于区左扩。
代码
//arr{3,4,6,7,5,3,5,8},num5
public static void func2(int[] arr,int num){int i0;int left-1;int rightarr.length;while (iright){if(arr[i]num){swap(arr,left,i);}else if(arr[i]num){i;}else{swap(arr,--right,i);}}System.out.println(Arrays.toString(arr));}
运行结果
[0, 0, 3, 5, 5, 7, 8, 6] 快排1.0
使用思考1的方式每次确认一个数的位置 public static void quickSort(int[] arr){if(arrnull || arr.length2){return;}quickSort(arr,0,arr.length-1);}
public static void quickSort(int[] arr,int l,int r){if(lr){//r所在位置的元素作为基准点int i partition(arr, l, r);quickSort(arr,l,i);quickSort(arr,i1,r);}}
public static int partition(int[] arr, int l, int r){int leftl-1;while(lr){if(arr[l]arr[r]){swap(arr,left,l);}else if(arr[l]arr[r]){l;}}swap(arr,left1,r);//left是小于区的边界return left;}
对于数组arr{1,2,3,4,5,6,7,8,9}最坏时间复杂度为O(N^2) 快排2.0
使用 思考 2) 的方式每次确认一种数的位置
代码
public static void quickSort(int[] arr){if(arrnull || arr.length2){return;}quickSort(arr,0,arr.length-1);}//选择数组中最后一位为 基准点public static void quickSort(int[] arr,int l,int r){if(lr){//p的大小为2是与最后一位数相等的数的左右边界int[] ppartition(arr,l,r);//左边继续quickSort(arr,l,p[0]-1);//右边继续quickSort(arr,p[1]1,r);}}
private static int[] partition(int[] arr, int l, int r) {int[] pnew int[2];//小于区域边界int lessl-1;//大于区域边界int morer;//当l达到大于边界时说明已经分类完成while(lmore){//l所在位置比基准点位置小arr[l]和小于区的下一个数交换小于区右扩lif(arr[l]arr[r]){swap(arr,less,l);}else if(arr[l]arr[r]){l;}else{//arr[l]arr[r]l位置上的值与大于区前一个位置上的值进行交换大于区左扩swap(arr,--more,l);}}//基准点所在当前数组的最后一位r和大于arr[r]上的第一个值的位置也就是大于区的边界进行交换。swap(arr,r,more);p[0]less1;//等于基准点的数的左边界p[1]more;//等于基准点的数的有边界//此时l~less 就是比基准点小的数more1~r就是比基准点大的数return p;}
如果我们选择的数组为 arr{1,2,3,4,5,6,7,8,9}那么最坏的时间复杂度为O(N^2) 快排3.0
就是在快排2.0的基础上添加了一个随机交换的操作保证不能人为的列出最坏执行情况
代码 //int[] arr{3,4,6,7,5,3,5,8};public static void quickSort(int[] arr){if(arrnull || arr.length2){return;}quickSort(arr,0,arr.length-1);}//选择数组中最后一位为 基准点public static void quickSort(int[] arr,int l,int r){if(lr){//随机选择一个位置的值与最后一位交换swap(arr,r,l(int)(Math.random()*(r-l1)));//p的大小为2是与最后一位数相等的数的左右边界int[] ppartition(arr,l,r);//左边继续quickSort(arr,l,p[0]-1);//右边继续quickSort(arr,p[1]1,r);}}
private static int[] partition(int[] arr, int l, int r) {int[] pnew int[2];//小于区域边界int lessl-1;//大于区域边界int morer;//当l达到大于边界时说明已经分类完成while(lmore){//l所在位置比基准点位置小arr[l]和小于区的下一个数交换小于区右扩lif(arr[l]arr[r]){swap(arr,less,l);}else if(arr[l]arr[r]){l;}else{//arr[l]arr[r]l位置上的值与大于区前一个位置上的值进行交换大于区左扩swap(arr,--more,l);}}//基准点所在当前数组的最后一位r和大于arr[r]上的第一个值的位置也就是大于区的边界进行交换。swap(arr,r,more);p[0]less1;//等于基准点的数的左边界p[1]more;//等于基准点的数的有边界//此时l~less 就是比基准点小的数more1~r就是比基准点大的数return p;}
运行结果
[3, 3, 4, 5, 5, 6, 7, 8]
时间复杂度O(N*log(N)) 堆排序
代码 /**int[] arr{4,2,3,1,7};heapSort(arr);System.out.println(Arrays.toString(arr));**/
/*** 堆排序* param arr 待排序的数组* 时间复杂度O(N*log(N))* 空间复杂度O(1)*/public static void heapSort(int[] arr){if(arrnull || arr.length2){return;}//先调用heapInsert将数组变为大根堆的结构for (int i 0; i arr.length; i) { //O(N)heapInsert(arr,i);//O(log(N))}
//如果仅仅是将数组变成大根堆结构的话这段代码要快一些
// for(int iarr.length-1;i0;i--){
// heapify(arr,i,arr.length);
// }/*** 然后每一次将堆的最大值所在位置为0与最后一个元素互换堆的长度减1然后使用heapify调整堆结构* 这样数组就从后往前依次有序起来了**/int heapSizearr.length;swap(arr,0, --heapSize);while (heapSize0){ //O(N)heapify(arr,0,heapSize);//O(log(N))swap(arr,0,--heapSize);//O(1)}}
/*** index上的值满足大顶堆的条件从下往上移动* param arr 数组* param index 要移动的元素* 时间复杂度取决于树的高度OlogN*/public static void heapInsert(int[] arr,int index){//index和index的父节点进行比较如果arr[index]arr[(index-1)/2]说明它比父节点的值要大就交换这父子元素的位置。否则while循环结束//当index0的时候index-1/2 0此时的条件不满足while循环就结束while(arr[index]arr[(index-1)/2]){swap(arr,index,(index-1)/2);index(index-1)/2;}}
/*** index 上的值满足大顶堆的条件从上往下移动* param arr 数组* param index 要移动的元素* param heapSize 堆的大小* 时间复杂度取决于树的高度OlogN*/public static void heapify(int[] arr,int index,int heapSize){//当前节点的左孩子节点int left2*index1;//当左孩子节点存在的时候while (leftheapSize){//选择左孩子和右孩子中大的一个int largest(left1) heapSize arr[left1]arr[left]?(left1):left;//选择父节点和孩子节点之间大的一个largestarr[largest]arr[index]?largest:index;//如果父节点是大的一个说明已经满足大顶堆的条件breakif(largestindex){break;}//交换父节点和孩子节点的值swap(arr,index,largest);//移动到交换后的孩子节点indexlargest;//当前节点的左孩子节点leftindex*21;}}
public static void swap(int[] arr,int i,int j){int tmparr[i];arr[i]arr[j];arr[j]tmp;}
运行结果
[1, 2, 3, 4, 7] 桶排序基数排序
代码 /*** int[] arr{1,21,32,14,57,83,64,100,101};* radixSort(arr);* System.out.println(Arrays.toString(arr));**/public static void radixSort(int[] arr){if(arrnull || arr.length2){return;}//maxbits(arr) 获取数组中最大数的长度radixSort(arr,0,arr.length-1,maxbits(arr));}
private static void radixSort(int[] arr, int L, int R, int digit) {//10进制final int radix10;int i0,j0;//有多少个数就准备多少个辅助空间int[] bucketnew int[R-L1];for(int d1;ddigit;d){//有多少位就进出几次/***10个空间* count[0] 当前d位是0的数字有多少个* count[1] 当前d位是0~1的数字有多少个* count[2] 当前d位是0~2的数字有多少个* count[3] 当前d位是0~3的数字有多少个* count[i] 当前d位是0~i的数字有多少个**/int[] countnew int[radix]; //count[0....9]for(iL;iR;i){//j获取当前arr[i]的第d位个、十、百、千.....数的值jgetDigit(arr[i],d);//对应第j位上的数加1。(0~9)count[j];}for(i1;iradix;i){//count[i]数组中的数在第d位上小于等于i的有多少count[i]count[i-1];}//从数组的右边开始遍历for(iR;iL;i--){jgetDigit(arr[i],d);//进桶bucket[count[j]-1]arr[i];count[j]--;}for(iL,j0;iR;i,j){arr[i]bucket[j];}}}
private static int getDigit(int i, int d) {int res0;while(d--!0){resi%10;i/10;}return res;}
private static int maxbits(int[] arr) {int maxInteger.MIN_VALUE;for (int i 0; i arr.length; i) {maxMath.max(max,arr[i]);}int res0;while (max!0){res;max/10;}return res;}
运行结果
[1, 14, 21, 32, 57, 64, 83, 100, 101]
时间复杂度O(N)空间复杂度O(N) 排序算法的稳定性
稳定性同样的个体之间如果不因为排序而改变相对次序那这个排序就是具有稳定性的否则就没有。
稳定性对于基本数据类型的数据没有什么作用但是对于引用类型的数据在排序的时候就有用了比如一个商品具有价格与好评这两个属性我们先根据价格排序然后根据好评排序如果排序的算法是具有稳定性的那么就可以形成一个物美价廉的商品排序。
排序算法时间复杂度空间复杂度是否可以实现稳定性选择排序O(N^2)O(1)否冒泡排序O(N^2)O(1)可插入排序O(N^2)O(1)可归并排序O(N*log(N))O(N)可快排随机O(N*log(N))O(log(N))否堆排O(N*log(N))O(1)否桶排O(N)O(N)可
目前还没有找到时间复杂度O(N*log(N))额外空间复杂度O(1)有可以实现稳定性的排序算法。 异或运算
异或运算 也叫做无进位运算当两个操作数相同时异或运算的结果为 0。当两个操作数不同时异或运算的结果为 1。
1011 ^ 1001 0010 0 ^ N N , N ^ N 0
1 0 1 11 0 0 1 0 0 1 0//异或操作满足交换律和结合率a^bb^aa^bca^(b^c)
当交换两个数的值时可以使用异或操作这样就不会产生额外的空间 Testpublic void swap(){int a1;int b2;
aa^b;ba^b;aa^b;System.out.println(aa\nbb);}
输出a2b1
原因
a1,b2
第一次异或 aa^b,bb --- a1^2,b1
第二次异或 aa^b,ba^b^ba --- a1^2,b1^2^2--因为2^20,所以b1^01
第三次异或 aa^b^a,ba --- a1^2^1(原本是a^b^b因为后面一个b在第二步异或的时候变成了a的值所以这里是1)--a1^1^20^22
所以a和b就完成了交换。
但是使用异或操作完成的交换功能在程序中只能作用于地址位置不同的两个对象如果是同一个地址位置来进行异或会把值抹为0 例存在一个int类型的数组
1其中有一种数出现了奇数次其余都出现了偶数次求这个奇数次的数 使用时间复杂度为 O(n)空间复杂度为O(1)。
使用一个整数0对数组中的每一个数进行异或运算因为异或运算不在乎数的顺序所以就是 0 ^ 所有的偶数次的数为0^ 奇数次的数(剩一个) --- 结果就是 0 ^ 一个奇数次的数 奇数次的数。
//int[] numsnew int[]{0,0,1,3,1,2,3};
public static void printOddTimesNum1(int[] nums){int eor0;for (int num : nums) {eoreor^num;}System.out.println(eor);}
/**输出为2
**/ 2有两种数出现了奇数次其余都出现了偶数次求这个偶数次的数
//int[] numsnew int[]{0,1,3,1,2,3};
public static void printOddTimesNum2(int[] nums){int eor0;/**eor 奇数1 ^ 奇数2因为奇数1和奇数2不相同所以eor一定不等于0这表示eor的32位二进制中至少有一位为1.那么在为1的这个二进制位置上奇数1和奇数2的值一定不同一定是其中一个为1另一个为0所以我们就可以先求出这个位 置然后再去与数组中的值进行异或得到其中一个奇数**/for (int num : nums) {eoreor^num;}/**这里就是来求出最右边为1的位置例如eor 10100 ~eor 01011 ~eor1 01100eor ~eor1 : 1010001100--- 00100所以最右边为1的位置就是001004**/int rightIndexeor ~eor1;int onlyOne0;for (int num : nums) {if((num rightIndex)1){//如果右边第4为为1才进行异或运算onlyOne最后得到的就是奇数1或者奇数2的值onlyOne onlyOne^num;}}System.out.println(num1:onlyOne\nnum2:(eor ^ onlyOne));}
//输出 num1:0
// num2:2 二分查找
1在一个有序数组中找某个数是否存在
//int resbinarysearch(nums,target,0,nums.length-1);
private static int binarysearch(Integer[] nums, Integer target,Integer left,Integer right) {if(leftright) return -1;int lleft;int rright;int mid(lr)1;if(nums[mid]target){return binarysearch(nums,target,left,mid-1);}else if(nums[mid]target){return binarysearch(nums,target,mid1,right);}
return mid;} 2在一个有序数组中找 某个数最左侧的位置
/**Integer[] nums2{1,1,1,1,1,2,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5};System.out.println(binarysearch2(nums2, 3, 0, nums2.length - 1));
**/
private static int binarysearch2(Integer[] nums, Integer target,Integer left,Integer right) {if(leftright) return -1;int lleft;int rright;int t0;while(lr){int mid(lr)1;if(nums[mid]target){/*** 找到了一个 target的数将位置记录下来* 不过也可能在这个数的左边还存在 target 的数* 所以就更新右边界,去左边继续寻找*/tmid;rmid-1;}else{//这里就是 nums[mid]的值比target要小更新左边界继续去数组右边去找lmid1;}}
return t;}
//输出10 3局部最小值问题 数组无序相邻的两个数不相等 局部最小定义arr[0] arr[1] 数组0位置的值就是局部最小arr[arr.length-1] arr[arr.length-2] 数组最后一个位置的值就是局部最小对于数组其他位置上的数 满足 arr[i-1] arr[i] arr[i1] i位置上的数就是局部最小 /**Integer[] nums3{1,0,1,3,6,5,1,2,3};System.out.println(binarysearch3(nums3));
**/
private static int binarysearch3(Integer[] nums) {int l0;int rnums.length-1;if(nums[l]nums[l1]) return l;if(nums[r]nums[r-1]) return r;//如果执行到了这里表示数组的两个边界都不是局部最小值那么在这数组之中一定存在一个局部最小值while(lr){int mid(lr)1;if(nums[mid]nums[mid-1] nums[mid]nums[mid]1){return mid;}if(nums[mid]nums[mid-1]){rmid-1;} else if (nums[mid]nums[mid1]) {lmid1;}}return -1;}
//输出 1 对数器
有一个你想要测的方法 a
实现复杂度不好但是容易实现的方法 b
实现一个随机样本产生器
把方法 a 和方法 b 跑相同的随机样本看看得到的结果是否一样。
如果有一个随机样本是的对比结果不一致打印样本进行人工干预改对方法 a 或 方法 b
当样本数量很多时对比测试是否依然正确如果依然正确就可以确定方法 a 已经正确
这里以插入排序作为方法ajava中本身提供的sort方法作为方法b
public static void main(String[] args) {int testTime500000;int maxSize100;int maxValue100;boolean succeedtrue;for(int i0;itestTime;i){int[] arr1generateRandomArray(maxSize,maxValue);int[] arr2copyArray(arr1);//对arr1数组深拷贝MySort(arr1);//插入排序 a方法comparator(arr2);//b方法if(!isEqual(arr1,arr2)){//如果排序后的两个方法中的值存在差异succeedfalse;break;}}System.out.println(succeed ? Nice:Fucking fucked);
int[] array generateRandomArray(maxSize, maxValue);System.out.println(Arrays.toString(array));MySort(array);System.out.println(Arrays.toString(array));
}
//随机生成一个长度位maxSize最大值为maxValue的int类型的数组public static int[] generateRandomArray(int maxSize,int maxValue){/*** Math.random() - [0,1) 所有的小数等概率返回一个 因为在计算机中数的位数是有限制的所以可以确定所有的小数在数学上就不行。* Math.random()*N - [0,N) 所有的小数等概率返回一个* (int)(Math.random()*N) - [0,N-1] 所有的整数等概率返回一个*/
int[] arrnew int[(int)((maxSize1)*Math.random())];//长度随机for(int i0;iarr.length;i){arr[i](int) ((maxValue1)*Math.random())-(int)(maxValue*Math.random());}return arr;}
//深拷贝
private static int[] copyArray(int[] arr1) {if(arr1null) return null;int[] arrnew int[arr1.length];for (int i 0; i arr1.length; i) {arr[i]arr1[i];}return arr;}
//插入排序
private static void MySort(int[] nums) {if(numsnull || nums.length2){return;}int lnums.length;for(int i1;il;i){for(int ji;j0;j--){if(nums[j]nums[j-1]){swap(nums,j,j-1);}else{break;}}}}
//交换
private static void swap(int[] nums, int i, int j) {int tmp nums[i];nums[i] nums[j];nums[j]tmp;}
//java提供的方法
private static void comparator(int[] arr2) {Arrays.sort(arr2);}
//比较两个数组中的内容是否完全一致
public static boolean isEqual(int[] arr1,int[] arr2){for (int i 0; i arr1.length; i) {if(arr1[i]!arr2[i]) return false;}return true;}
## 比较器
返回负数的时候认为第一个参数排在前面 ----- 升序
返回正数的时候认为第二个参数排在前面 ----- 降序
返回0的时候谁排在前面无所谓
PriorityQueueInteger heap new PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o1-o2;}}); 递归
递归求数组中的最大值
剖析递归行为何递归行为时间复杂度的估算
用递归方法找一个数组中的最大值系统上到底是怎么做的
master公式的使用
T(N) a*T(N/b) O(N^d)
1log(b,a) d -- 时间复杂度为O(N^log(b,a))
2log(b,a) d -- 时间复杂度为O(N^d * logN)
3log(b,a) d -- 时间复杂度为O(N^d)
递归求数组中的最大值
public static int findMax(int[] arr,int left,int right){if(leftright){return arr[left];}int midleft((right-left)1);int leftMaxfindMax(arr,left,mid);int rightMaxfindMax(arr,mid1,right);return Math.max(leftMax,rightMax);}
执行流程 随着每一次findMax函数的调用都会在java虚拟机栈中创建一个栈帧等待每一个栈帧中的内容执行完毕后返回结果给上一层调用它的栈帧这样一层层的调用到最后最开始的那一个栈帧对应的函数就可以得到最终的结果。
根据master公式我们可以得出下面这个数据
T(N) 2T(N/2)O(1)a2,b2,d0a2因为一个函数中包含了两次子函数的调用b2因为调用一次子函数的数据是父函数的一半d0因为除了调用子函数之外的代码的时间复杂度是常数项所以 log(a,b)d所以T(N)T(N^log(1,1))T(N)跟直接循环得到数组中的最大值的时间复杂度结果一样
堆
堆结构
堆结构就是用数组实现的完全二叉树结构完全二叉树是一种特殊的二叉树其中除了最后一层外每一层的节点都被完全填满并且最后一层的节点都靠左对齐。
完全二叉树中如果每颗子树的最大值都在顶部就是大根堆 完全二叉树中如果每颗子树的最小值都在顶部就是小根堆 堆结构的heapInsert与heapify操作
/*** index上的值满足大根堆的条件从下往上移动* param arr 数组* param index 要移动的元素* 时间复杂度取决于树的高度OlogN*/public static void heapInsert(int[] arr,int index){//index和index的父节点进行比较如果arr[index]arr[(index-1)/2]说明它比父节点的值要大就交换这父子元素的位置。否则while循环结束//当index0的时候index-1/2 0此时的条件不满足while循环就结束while(arr[index]arr[(index-1)/2]){swap(arr,index,(index-1)/2);index(index-1)/2;}}
/*** index上的值满足大根堆的条件从上往下移动* param arr 数组* param index 要移动的元素* param heapSize 堆的大小* 时间复杂度取决于树的高度OlogN*/public static void heapify(int[] arr,int index,int heapSize){//当前节点的左孩子节点int left2*index1;//当左孩子节点存在的时候while (leftheapSize){//选择左孩子和右孩子中大的一个int largest(left1) heapSize arr[left1]arr[left]?(left1):left;//选择父节点和孩子节点之间大的一个largestarr[largest]arr[index]?largest:index;//如果父节点是大的一个说明已经满足大顶堆的条件breakif(largestindex){break;}//交换父节点和孩子节点的值swap(arr,index,largest);//移动到交换后的孩子节点indexlargest;//当前节点的左孩子节点leftindex*21;}}
堆结构的增大和减少
堆结构的增大将增加的值放到数组的最后一位然后调用heapInsert函数
堆结构的减少将要删除的元素所在位置记录为index并且和最后一位互换然后数组长度减1调用Heapify函数
所以也可以说堆结构就是优先级队列结构。
在Java中封装了一个优先级队列PriorityQueue
PriorityQueueInteger heap new PriorityQueue();
PriorityQueue默认的就是使用小根堆实现的也可以使用比较器自己定义。
如果在我们的需求中仅仅只是对堆中的数据进行add和poll的话就可以使用PriorityQueue这样的效率也比较高。
比如
已知一个几乎有序的数组几乎有序是指如果把数组排好顺序的话每个元素移动的距离不超过k并且k相对于数组的长度来说比较小请选择一个合适的排序算法针对这个数据进行排序。
代码
/**
* int[] arr2{2,3,1,4,6,5};
* heapSortByK(arr2,2);
* System.out.println(Arrays.toString(arr2));
**/
public static void heapSortByK(int[] arr,int k){PriorityQueueInteger heap new PriorityQueue();int index0;/*** 先将数组中前k的元素加入到堆中这前k的元素中一定包含数组0位置上正确的数字就是数字中的最小值*/for(;indexMath.min(k,arr.length);index){heap.add(arr[index]);}int i0;/*** 每一次将数组中k位置后面的元素加入堆中并弹出堆顶的位置* 弹出的元素就是数字i位置上应该放的元素。*/for(;indexarr.length;index){heap.add(arr[index]);arr[i]heap.poll();}while (!heap.isEmpty()){arr[i]heap.poll();}}
运行结果
[1, 2, 3, 4, 5, 6]
不过如果我们的业务需要修改堆中的结构比如删除或修改一个堆中的数据那么使用PriorityQueue就不是一个最好的选择因为PriorityQueue它不能确定我们所修改的位置只能一个一个的遍历堆中的数据判断这个数据是否需要进行heapify这样PriorityQueue的效率就不高。如果我们有这样的需求就需要我们自己手写堆我们手写的堆在修改堆结构时可以知道是那里发生了修改直接在修改的位置进行heapify即可。
