初级--03---二分、复杂度、哈希表和有序表

文章目录二分法题目1测试-----制造对数器int mid (L R) / 2; 有可能int溢出优化为: int mid L ((R - L) 1);题目2局部最小值问题时间复杂度基础--04----时间、空间复杂度哈希表哈希表可以看成一个(K V)表哈希表的增删改查,时间复杂度都可以看成 O(1)哈希表分类:HashMap基础类型 : int double char string ------按值传递对象类型 : int double char string ------引用传递有序表TreeMap的增删改查,时间复杂度都可以看成 O(n)java数据结构TreeMapTreeMap 的key 一定要能够比较,不然会报错二分法题目1// arr保证有序publicstaticbooleanfind(int[]arr,intnum){if(arrnull||arr.length0){returnfalse;}intL0;intRarr.length-1;while(LR){intmid(LR)/2;if(arr[mid]num){returntrue;}elseif(arr[mid]num){Lmid1;}else{Rmid-1;}}returnfalse;}测试-----制造对数器packagemain.java.newcode;importjava.util.Arrays;publicclassCode01_BSExist{// arr保证有序publicstaticbooleanfind(int[]arr,intnum){if(arrnull||arr.length0){returnfalse;}intL0;intRarr.length-1;while(LR){intmid(LR)/2;if(arr[mid]num){returntrue;}elseif(arr[mid]num){Lmid1;}else{Rmid-1;}}returnfalse;}// for testpublicstaticbooleantest(int[]sortedArr,intnum){for(intcur:sortedArr){if(curnum){returntrue;}}returnfalse;}// for testpublicstaticint[]generateRandomArray(intmaxSize,intmaxValue){int[]arrnewint[(int)((maxSize1)*Math.random())];for(inti0;iarr.length;i){arr[i](int)((maxValue1)*Math.random())-(int)(maxValue*Math.random());}returnarr;}publicstaticvoidmain(String[]args){inttestTime500000;intmaxSize10;intmaxValue100;booleansucceedtrue;for(inti0;itestTime;i){int[]arrgenerateRandomArray(maxSize,maxValue);Arrays.sort(arr);intvalue(int)((maxValue1)*Math.random())-(int)(maxValue*Math.random());if(test(arr,value)!find(arr,value)){System.out.println(出错了);succeedfalse;break;}}System.out.println(succeed?Nice!:Fucking fucked!);}}int mid (L R) / 2; 有可能int溢出优化为:int mid L ((R - L) 1);// arr保证有序publicstaticbooleanfind(int[]arr,intnum){if(arrnull||arr.length0){returnfalse;}intL0;intRarr.length-1;while(LR){intmidL((R-L)1);if(arr[mid]num){returntrue;}elseif(arr[mid]num){Lmid1;}else{Rmid-1;}}returnfalse;}题目2// arr有序的num 最左publicstaticintmostLeftNoLessNumIndex(int[]arr,intnum){if(arrnull||arr.length0){return-1;}intL0;intRarr.length-1;intans-1;while(LR){intmid(LR)/2;if(arr[mid]num){ansmid;Rmid-1;}else{Lmid1;}}returnans;}// 在arr上找满足value的最右位置publicstaticintnearestIndex(int[]arr,intvalue){intL0;intRarr.length-1;intindex-1;// 记录最右的对号while(LR){intmidL((R-L)1);if(arr[mid]value){indexmid;Lmid1;}else{Rmid-1;}}returnindex;}局部最小值问题publicclassCode04_BSAwesome{// arr 整体无序// arr 相邻的数不相等publicstaticintoneMinIndex(int[]arr){if(arrnull||arr.length0){return-1;}intNarr.length;if(N1){return0;}if(arr[0]arr[1]){return0;}if(arr[N-1]arr[N-2]){returnN-1;}intL0;intRN-1;// L...R 肯定有局部最小while(LR-1){intmid(LR)/2;if(arr[mid]arr[mid-1]arr[mid]arr[mid1]){returnmid;}else{if(arr[mid]arr[mid-1]){Rmid-1;}else{Lmid1;}}}returnarr[L]arr[R]?L:R;}// 生成随机数组且相邻数不相等publicstaticint[]randomArray(intmaxLen,intmaxValue){intlen(int)(Math.random()*maxLen);int[]arrnewint[len];if(len0){arr[0](int)(Math.random()*maxValue);for(inti1;ilen;i){do{arr[i](int)(Math.random()*maxValue);}while(arr[i]arr[i-1]);}}returnarr;}// 也用于测试publicstaticbooleancheck(int[]arr,intminIndex){if(arr.length0){returnminIndex-1;}intleftminIndex-1;intrightminIndex1;booleanleftBiggerleft0?arr[left]arr[minIndex]:true;booleanrightBiggerrightarr.length?arr[right]arr[minIndex]:true;returnleftBiggerrightBigger;}publicstaticvoidprintArray(int[]arr){for(intnum:arr){System.out.print(num );}System.out.println();}publicstaticvoidmain(String[]args){intmaxLen100;intmaxValue200;inttestTime1000000;System.out.println(测试开始);for(inti0;itestTime;i){int[]arrrandomArray(maxLen,maxValue);intansoneMinIndex(arr);if(!check(arr,ans)){printArray(arr);System.out.println(ans);break;}}System.out.println(测试结束);}}时间复杂度基础–04----时间、空间复杂度哈希表哈希表可以看成一个(K V)表哈希表的增删改查,时间复杂度都可以看成 O(1)哈希表分类:引用传递按值传递HashMap基础类型 : int double char string ------按值传递publicstaticvoidmain(String[]args){HashMapInteger,Stringmap2newHashMap();map2.put(1234567,我是1234567);Integera1234567;Integerb1234567;System.out.println(ab);System.out.println(map2.containsKey(a));System.out.println(map2.containsKey(b));}对象类型 : int double char string ------引用传递importjava.util.HashMap;importjava.util.TreeMap;publicclassCode05_HashMapTreeMap{publicstaticclassNode{publicintvalue;publicNode(intv){valuev;}}// (K V)表publicstaticvoidmain(String[]args){Nodenode1newNode(1);Nodenode2newNode(1);HashMapNode,Stringmap3newHashMap();map3.put(node1,我进来了);System.out.println(map3.containsKey(node1));System.out.println(map3.containsKey(node2));}}有序表TreeMap的增删改查,时间复杂度都可以看成 O(n)java数据结构TreeMappublicstaticvoidmain(String[]args){TreeMapInteger,StringtreeMap1newTreeMap();treeMap1.put(3,我是3);treeMap1.put(0,我是3);treeMap1.put(7,我是3);treeMap1.put(2,我是3);treeMap1.put(5,我是3);treeMap1.put(9,我是3);System.out.println(treeMap1.containsKey(7));System.out.println(treeMap1.containsKey(6));System.out.println(treeMap1.get(3));treeMap1.put(3,他是3);System.out.println(treeMap1.get(3));treeMap1.remove(3);System.out.println(treeMap1.get(3));System.out.println(treeMap1.firstKey());System.out.println(treeMap1.lastKey());// 5 离5最近的key告诉我System.out.println(treeMap1.floorKey(5));// 6 离6最近的key告诉我System.out.println(treeMap1.floorKey(6));// 5 离5最近的key告诉我System.out.println(treeMap1.ceilingKey(5));// 6 离6最近的key告诉我System.out.println(treeMap1.ceilingKey(6));// Node node3 new Node(3);// Node node4 new Node(4);// TreeMapNode, String treeMap2 new TreeMap();// treeMap2.put(node3, 我是node3);// treeMap2.put(node4, 我是node4);}TreeMap 的key 一定要能够比较,不然会报错importjava.util.TreeMap;publicclassCode05_HashMapTreeMap{publicstaticclassNode{publicintvalue;publicNode(intv){valuev;}}publicstaticvoidmain(String[]args){TreeMapInteger,StringtreeMap1newTreeMap();Nodenode3newNode(3);Nodenode4newNode(4);TreeMapNode,StringtreeMap2newTreeMap();treeMap2.put(node3,我是node3);treeMap2.put(node4,我是node4);}}