二分法
入门题目
- 有序数组中找到num
-
package class03; import java.util.Arrays; // 有序数组中找到num public class Code_BSExist { // arr保证有序 public static boolean find(int[] arr, int num) { // 二分法，有缺陷 if (arr == null || arr.length == 0) { // 边界条件 return false; } int L = 0; // 左边界 int R = arr.length - 1; // 有边界 // arr[L....R] 即arr[0...arr.length-1] 这个范围找num while (L <= R) { // <= 是有效范围 int mid = (L + R) / 2; //中点位置 if (arr[mid] == num) { return true; // 找到了 正确 } else if (arr[mid] < num) { // 小于的情况，左边的丢掉，继续找，新的L是mid+1 L = mid + 1; } else { // 大于num的情况，右侧不可能，继续找，新的R是mid-1 R = mid - 1; } } return false; // 以上情况都没找到return false } // for test public static boolean test(int[] arr, int num) { // 对数器 for (int cur : arr) { if (cur == num) { return true; } } return false; } public static int[] generateRandomArray(int maxLen, int maxValue) { int[] arr = new int[(int) ((maxLen + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } public static void main(String[] args) { int testTime = 500000; int maxLen = 10; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr = generateRandomArray(maxLen, maxValue); Arrays.sort(arr); // 排序 int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); if (test(arr, value) != find(arr, value)) { System.out.println("出错了!"); succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); } }
-
- 有序数组中找到>=num最左的位置
-
package class03; import java.util.Arrays; //在有序数组中找到>=num最左的位置 // [1,2,2,2,3,4,5,6,7] >=2 的最左位置的数是索引为1的数2，>=4 的最左位置是索引为5的数4 public class Code_BSNearLeft { // arr有序，找>=num 最左 public static int mostLeftNoLessNumIndex(int[] arr, int num) { if (arr == null || arr.length == 0) { return -1;// -1代表不在里面，返回-1代表没这个概念 } int L = 0; int R = arr.length - 1; int ans = -1; // 最晚发生的ans，令他等于-1 while (L <= R) {// 范围 // 在while里面会更新ans，直到找到符合最左位置的索引，它就跳出循环，return 它 int mid = (L + R) / 2; if (arr[mid] >= num) { ans = mid; // 往左找，需要更新 R = mid - 1; } else { // arr[mid]<num // 中点小于num，ans不更新 L = mid + 1;// 左边砍掉 } } return ans; // 如果没有>=这个数，它将以-1返回，即没这个数。 } // for test public static int test(int[] arr, int value) { //对数器 for (int i = 0; i < arr.length; i++) { // 从左边开始遍历 if (arr[i] >= value) {// 第一个大于等于value的返回其索引位置 return i; } } return -1; } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) (Math.random() * (maxSize + 1))]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue)); } return arr; } public static void printArray(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void main(String[] args) { int maxSize = 10; int maxValue = 100; int testTime = 500000; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr = generateRandomArray(maxSize, maxValue); Arrays.sort(arr);// 排序 int value = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue)); if (test(arr, value) != mostLeftNoLessNumIndex(arr, value)) { printArray(arr); System.out.println(value); System.out.println(test(arr, value)); System.out.println(mostLeftNoLessNumIndex(arr, value)); succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked");// 无问题Nice，有问题Fucking fucked } }
-
- 有序数组中找到<=num最右的位置
-
package class03; import java.util.Arrays; public class Code_BSNearRight { //在有序数组中找到<=num最右的位置 // [1,2,2,2,3,4,5,6,7] <=2 的最左位置的数是索引为3的数2，<=4 的最左位置是索引为5的数4 // arr有序，找<=num 最右 public static int mostRightNoLessNumIndex(int[] arr, int num) { if (arr == null || arr.length == 0) { return -1; } int L = 0; int R = arr.length - 1; int ans = -1; while (L <= R) { int mid = (L + R) / 2; if (arr[mid] <= num) { ans = mid; // 更新ans L = mid + 1; // <=num,左边砍掉，找最右的数 } else {//arr[mid]>num R = mid - 1;// 右边砍掉 } } return ans; // 返回正确的结果 } //for test public static int test(int[] arr, int value) {// 对数器 for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] <= value) { return i; } } return -1; } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) (Math.random() * (maxSize + 1))]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue)); } return arr; } public static void printArray(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void main(String[] args) { int maxSize = 10; int maxValue = 100; int testTime = 500000; // 测试次数 boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr = generateRandomArray(maxSize, maxValue); Arrays.sort(arr); int value = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue)); if (test(arr, value) != mostRightNoLessNumIndex(arr, value)) { printArray(arr); System.out.println(value); System.out.println(test(arr, value)); System.out.println(mostRightNoLessNumIndex(arr, value)); succeed = false; break; } } System.out.println(succeed ? "Nice" : "Fucking fucked"); } }
-
- 局部最小值问题
-
package class03; // 局部最小值问题(无序数组) // 一个数组，无序，数组有条件，任意两个相邻的数之间不相等 [1,2,3,2,3,4]... /* * 局部最小定义： * 1)[0]<[1] 0位置的数是局部最小 * 2)[N-1]<[N-2] N-1位置的数是局部最小 * 3）左>[i]<右 i位置的数局部最小 * 总结以上三点，0~N-1必存在局部最小。0~1下降，N-2~N-1上升，所以必有 * 问题：返回以上其中一个局部最小即可 * */ public class Code_BSAwesome { // arr整体无序，要满足相邻的数不相等 public static int oneMidIndex(int[] arr) { if (arr == null || arr.length == 0) {// 边界条件 return -1; } int N = arr.length; if (N == 1) { return 0;// 一个数，默认0位置最小 } if (arr[0] < arr[1]) { return 0; } if (arr[N - 1] < arr[N - 2]) { return N - 1; } //N > 2 的时候 // 二分 int L = 0; int R = N - 1; // L~R肯定有局部最小 while (L < R - 1) { // （边界条件） 为什么是L<R-1:因为L~R之间要3个数或3个数以上 int mid = (L + R) / 2; // 中点 if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) { // 左>[i]<右 return mid; // 三个数（包括三个数）以上返回mid } else { /* * 不同时小,(我是arr[mid]) * 1)左 > 我 我 > 右 * 2)左 < 我 我 < 右 * 3)左 < 我 我 > 右 * */ // 如果是2、3情况，不用管右边，在左边继续找就行 if (arr[mid] > arr[mid - 1]) { // 砍掉右边,R这时候来到mid-1位置 R = mid - 1;// 更新R的位置 } else { // 否则就是1情况。 arr[mid] > arr[mid+1]（必定） // 砍掉左边,L这时候来到mid+1位置 L = mid + 1;// 更新L的位置 } } } // L~R出来之后就是L>=R-1,要么两个数，要么只有一个数 return arr[L] < arr[R] ? L : R;// 如果arr[L]<arr[R] 就返回L，否则是R（如果只有L和R两个相邻位置的数，谁小就返回谁（一定对）） // [3,2,3,2,3] 二分之后只有[3,2]，类似这种情况 } // 生成随机数组，且相邻数不相等 public static int[] randomArray(int maxLen, int maxValue) { int len = (int) (Math.random() * maxLen); int[] arr = new int[len]; // 相邻数不相等 if (len > 0) { arr[0] = (int) (Math.random() * maxValue); for (int i = 1; i < len; i++) { do { arr[i] = (int) (Math.random() * maxValue); } while (arr[i] == arr[i - 1]); // 如果相邻数相等，它就返回重做 } } return arr; } // 测试 public static boolean check(int[] arr, int minIndex) { if (arr.length == 0) { return minIndex == -1; } int left = minIndex - 1; // 定义局部最小左边的位置 int right = minIndex + 1; // 定义局部最小右边的位置 boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true; // 如果 left >= 0 时(有效位置)，看是不是左边位置的数大于我，<0就越界，则无数不影响 boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true; // 如果 left < arr.length 时(有效位置)，看是不是右边位置的数大于我，>arr.length就越界，则不管 return leftBigger && rightBigger; // 同时满足 } public static void printArray(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int testTime = 1000000; int maxLen = 10; int maxValue = 200; System.out.println("测试开始"); for (int i = 0; i < testTime; i++) { int[] arr = randomArray(maxLen, maxValue); int ans = oneMidIndex(arr); if (!check(arr, ans)) { // 如果有问题就打印以下内容 printArray(arr); // 数组 System.out.println(ans); // 位置 break; } } System.out.println("测试结束"); } }
-
时间复杂度
分析选择、冒泡、插入排序的时间复杂度
- 等差数列求和公式
- 以上公式展开
- n^2/2-(1/2-a1)n
- 时间复杂度定义：整个表达式中最高阶的东西，就是它的复杂度，例如：冒泡的是O(n^2)
- 例1）：1/100 n^2 + 1/500 n + 4 时间复杂度 O(n^2)
- 例2）：1000万*n + 5000万 时间复杂度O(n)
- 时间复杂度在于数据量很大的情况下，怎么去描述算法时间的关系。 O(n^2) < O(n)，O(n) 就是比 O(n^2)好
- 冒泡 可以写成 = a*n^2 + b*n + c a , b , c 是常数 O(n^2)
- 在二分中，它的时间复杂度是 O(㏒2 n) log以2为底n，n=2^? , 0~n 每次砍一半, 最接近n的问号就是它最多砍的次数
- 有的时候底数会省略，直接是O(log n)
- 常数操作是 O(1) （必定的）
- 要假设最差情况估计出来，跟n的关系，不能假设最好的情况，这才叫时间复杂度，才能是O(?)
常见时间复杂度列表
- 从好到坏
- O(1)→O(logn)→O(n)→O(n*logn)→O(n^2)→O(n^3)→O(n^k)→O(2^n)→O(3^n)→O(k^n)…..→O(n!)
动态数组
- 动态数组是什么？
- Arraylist（Java）
- 例子：
- [ ]原先是固定长度为4的数组a
- 现在往里面放数，发现长度不够放了，在Arraylist，它会扩成[ ]长度为8的数组b，把数组a的数拷贝下来，并加新放的数
- 如果还不够，它会继续扩成长度为16的数组c，把b数组的数拷贝下来，并加新放的数。。。。这就是Arraylist
- 动态数组的使用和扩容
- 如果是固定数组，在固定数组找index，它的复杂度是 O(1)
- 现在是Arraylist，它会扩容，讨论扩容这件事会不会影响Arraylist的表现？
- 动态数组的扩容与时间复杂度分析
- 如果加入N个数，扩容的总代价是多少
- O(N)
- 如果加入1个数，扩容的代价是多少
- O(1) （均摊一下）
- 从时间复杂度角度上看，动态数组和固定数组的没有影响，跟固定数组一样好。
- 如果加入N个数，扩容的总代价是多少
哈希表和有序表
- code
-
package class03; import sun.reflect.generics.tree.Tree; import java.util.HashMap; import java.util.TreeMap; public class Code_HashMapTreeMap { public static class Node { public int value; public Node(int v) { value = v; } } // (K,V)表，不管加了多少条数据，它都是常数时间，时间复杂度O(1),固定时间，它的时间比较大 public static void main(String[] args) { // String在HashMap表是按值传递的 // 按值传递，一张哈希表占一个字节 HashMap<String, String> map = new HashMap<>(); map.put("lisifang", "我是李四方"); // 新增数据 System.out.println(map.containsKey("guojiahui")); // 查询是否有guojiahui这个key，上面刚加，所以一定有返回true System.out.println(map.containsKey("guo")); // 无，则返回false System.out.println(map.get("guojiahui")); // 取出K对应的V我是李四方 map.put("guojiahui", "他1是李四方"); // 更新数据 System.out.println(map.get("guojiahui")); // 他是李四方 // put既是新增操作也是更新value操作 // map.remove("guojiahui"); // 删除 // System.out.println(map.containsKey("guojiahui")); // false // System.out.println(map.get("guojiahui")); // 空 null值 String test1 = "guojiahui"; String test2 = "guojiahui"; System.out.println(map.containsKey(test1)); System.out.println(map.containsKey(test2)); HashMap<Integer, String> map2 = new HashMap<>(); map2.put(1234567, "我是1234567"); Integer a = 1234567; Integer b = 1234567; System.out.println(a == b); // false == 比较a的内存地址和b的内存地址是不是一块内存区域。 比较a和b的值用a.equals(b) // 哈希表中不管你的内存地址，只要你的值相等，它就存在 // Integer Double Float String Char 在哈希表中全部按值传递 System.out.println(map2.containsKey(a)); // true System.out.println(map2.containsKey(b)); // true // 非基础类型，非原生类型，哈希表它按引用传递 // 按引用传递，它一个地址占8字节，一张哈希表总共两个，所以它占16字节 Node node1 = new Node(1); Node node2 = new Node(1); HashMap<Node, String> map3 = new HashMap<>(); map3.put(node1,"我进来了"); System.out.println(map3.containsKey(node1)); // true 在 System.out.println(map3.containsKey(node2)); // false 不在 System.out.println("====================="); // 有序表,它的时间复杂度全部是O(logN),比哈希表慢 TreeMap<Integer,String> treeMap1 = new TreeMap<>(); 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)); // true 存在 System.out.println(treeMap1.containsKey(6)); // false 不存在 System.out.println(treeMap1.get(3)); // 我是3 treeMap1.put(3,"他是3"); //更新 System.out.println(treeMap1.get(3)); // 他是3 treeMap1.remove(3); // 删除 System.out.println(treeMap1.get(3)); // null // 与哈希表不同的 // 内部排好序 System.out.println(treeMap1.firstKey()); // 0 System.out.println(treeMap1.lastKey()); // 9 // <=5 离5最近的key告诉我 System.out.println(treeMap1.floorKey(5)); // 5 // <=6 离6最近的key告诉我 System.out.println(treeMap1.floorKey(6)); // 5 // >=5 离5最近的key告诉我 System.out.println(treeMap1.ceilingKey(5)); // 5 // >=6 离6最近的key告诉我 System.out.println(treeMap1.ceilingKey(6)); // 7 // 以下会报错，自己搞出来的结构，key不可比较，需要自己定义好key // 原生结构它会自己定义好来 Node node3 = new Node(3); Node node4 = new Node(4); TreeMap<Node,String> treeMap2 = new TreeMap<>(); treeMap2.put(node3,"我是node3"); treeMap2.put(node4,"我是node4"); } }
-
