唐山做企业网站网上营销
算法复杂度
- 不依赖于环境因素
- 事前分析法
- 计算最坏情况的时间复杂度
- 每一条语句的执行时间都按照t来计算
时间复杂度
- 大O表示法
- n = 数据量 ; f(n) = 实际的执行条数
- 当存在一个n0 , 使得 n > n0,并且 c * g(n) 恒> f(n) : 渐进上界(算法最坏的情况)
- 那么f(n)的时间复杂度 => O(g(n))
- 大O表示法
- f(n)中的常数量省略
- f(n)中较低次幂省略
- log2(n) => log(n)
- 常见的表示
- O(1) > O(log(n)) >> O(n) > O(nlog(n)) >> O(n2) > O(2^n) >> O(n!)
空间复杂度
- 除原始参数以外,额外空间成本
二分查找
基础版
-
步骤
- 有序数组A , 目标值target
- 左右索引值 : i = 0 , j = n - 1;
- 判断 i > j => 结束查找,没找到
- 中间索引 m = ( i + j) / 2 : 整形自动向下取整
- 判断 m > target : j = m -1; -> 跳到第三步继续执行
- 判断 m < target : i = m + 1; -> 跳到第三步继续执行
- 判断 m = target : 得到结果结束程序,返回索引值
-
代码如下
/*** 编写二分查找方法* @param A : 有序数组a* @param target : 目标查找值* @return 返回索引值*/public static int binarySearchBasic(int[] A, int target) {// 定义左右指针int i = 0, j = A.length - 1;// 定义循环条件while (i <= j) {// 定义中间指针m// int m = (i + j) / 2; int m = (i + j) >>> 1; // 判断A[m] 值 与 target值if (target < A[m]){// 中间值大 : 指针[m , j]中的值都会比target值大j = m - 1;} else if (A[m] < target){// 中间值小 : 指针[i , m]中的值都会比target值小i = m + 1;} else {// A[m] == target: 得到结果,结束循环,返回mreturn m;}}//i > j : 结束循环return -1; // 结束循环,返回-1} -
问题一 : 代码while循环中为什么是i <= j , 而不是 i < j ?
答 : 首先 代码return -1; 本身表示的就是在 i>j 的情况下结束,没有找到,返回-1; , 那么相反对应的循环内就应该为 i <= j
其次, while(i < j ) 表示的是 只有i,j中间的m会参与比较 ; 而while(i <= j) : 表示 i , j所指向的元素 也会参与比较. 当i == j 的时候, m = i = j = (i + j) /2
-
问题二: 代码 int m = (i + j) / 2; 是否有问题?
答: 有问题.
假设 j 的值为整数类型最大值 (Integer.MAX_VALUE - 1) , 并且target值在数组的右侧 (target > A[m]) , 那么我们就需要将 索引i 的值调到m的右侧
即 : i = (i + j) /2 + 1; j = 整数类型最大值 = Integer.MAX_VALUE - 1;
那么根据Java int类型的特性, Java二进制首位为符号位,则会导致下一次进行 m = (i + j) / 2 的时候,使m成为负数
解决办法: 无符号右移运算符 数字 >>> 位数n
在二进制中,二进制码整体向右平移指定位数n就相当于n / 2n , 数字 >>> 1 => 数字 / 2运算取整
改动版
-
步骤
- 让右指针作为边界,必须不参与比较运算
- 循环不能有i=j的情况,如果i=j的话,则会造成m = i = j = (i + j) / 2 , 则不符合第一点j不参与比较运算的条件
- 当m指针所对应的值 > target值时,让j指针=m , 因为m指针对应的值已经参与过比较,并且肯定不等于target值,可作为边界不参与比较运算.
- 如果还是j = m - 1情况, m - 1的指针存在这等于target的可能,于第一点让j作为边界条件不服.
- 并且,当j= m - 1 , 如果要查找的target值不在数组A中时,会出现死循环的情况
-
代码如下
public static int binarySearchAlter(int[] A, int target) {// 改动一: 其中右指针j作为边界, 必须不参与运算比较int i = 0, j = A.length;// 定义循环条件 , 改动二: 由于不让j指针值参与比较, 故不需要i=j的情况,当i=j时,j被带着参与了比较,当target值不是数组值的时候,会导致死循环的情况while (i < j) {int m = (i + j) >>> 1;if (target < A[m]) {// 改动三: j作为边界,不参与比较.故当判断出来target值在m指针左侧时,m指针对应值已经判断过了,不可能和target相等,让j=m,及让j作为一个不可能相等的边界使用j = m;} else if (A[m] < target) {i = m + 1;} else {return m;}}return -1;}
平衡版
-
代码如下
/*** 二分查找平衡版** @param A : 有序数组a* @param target : 目标查找值* @return 返回索引值*/public static int binarySearchBalance(int[] A, int target) {// 定义左右边界,左边i指针对应的值可能target , 右指针j作为边界, 必须不参与运算比较int i = 0, j = A.length;// 定义循环条件 , 目的为缩小比较范围,将最后比较功能放到循环以外// 由i < j => 0 < j - i 改为 1 < j - i; 表示[i , j]区间内待比较的个数是否有1个以上while (1 < j - i) {// 定义中间索引int m = (i + j) >>> 1;if (target < A[m]) {// j作为右边界,不参与比较.故当判断出来target值在m指针左侧时,m指针对应值已经判断过了,不可能和target相等,让j=m,及让j作为一个不可能相等的边界使用j = m;} else {// 及 A[m] <= target的情况,及 i指针对应的值是有可能为target结果的i = m;}}// 将缩减范围后剩余的一个索引i所对应的值与target进行比较if (A[i] == target){return i;} else {return -1;}}
二分查找-Java版源码
- 通过Arrays.binarySearch(int[] arr, int key);方法调用
/*** Searches the specified array of ints for the specified value using the* binary search algorithm. The array must be sorted (as* by the {@link #sort(int[])} method) prior to making this call. If it* is not sorted, the results are undefined. If the array contains* multiple elements with the specified value, there is no guarantee which* one will be found.** @param a the array to be searched* @param key the value to be searched for* @return index of the search key, if it is contained in the array;* otherwise, <code>(-(<i>insertion point</i>) - 1)</code>. The* <i>insertion point</i> is defined as the point at which the* key would be inserted into the array: the index of the first* element greater than the key, or {@code a.length} if all* elements in the array are less than the specified key. Note* that this guarantees that the return value will be >= 0 if* and only if the key is found.*/public static int binarySearch(int[] a, int key) {return binarySearch0(a, 0, a.length, key);}// Like public version, but without range checks.private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {int low = fromIndex;int high = toIndex - 1;while (low <= high) {int mid = (low + high) >>> 1;int midVal = a[mid];if (midVal < key)low = mid + 1;else if (midVal > key)high = mid - 1;elsereturn mid; // key found}return -(low + 1); // key not found.}
二分查找对于重复元素查找的处理
获取重复最左侧索引值
-
步骤
- 添加一个结果变量索引值,用来存储当m索引值与target相等时,存储m索引值 ,
- 当相等时,j继续缩小边界,程序继续直到程序结束,获取最左侧结果
- i > j : 结束循环 , 返回结果索引值
-
代码如下
public static int binarySearchLeftMost(int[] A, int target) {// 定义左右指针int i = 0, j = A.length - 1;// 定义结果变量索引值int resIndex = -1;// 定义循环条件while (i <= j) {// 定义中间指针mint m = (i + j) / 2;// 判断A[m] 值 与 target值if (target < A[m]){// 中间值大 : 指针[m , j]中的值都会比target值大j = m - 1;} else if (A[m] < target){// 中间值小 : 指针[i , m]中的值都会比target值小i = m + 1;} else {// A[m] == target: 将结果存储到结果索引值中, 并将右侧边界缩小,继续进行程序,直到程序结束,获取最左侧结果resIndex = m;j = m - 1;}}//i > j : 结束循环 , 返回结果索引值return resIndex;} -
获取重复最右侧索引值 : 将上放代码第20行 j = m - 1; => 改为 i = m + 1; 即可
修改返回值意义
-
获取<= 索引值 最靠右的索引值结果 , 代码如下:
public static int binarySearchRightMost1(int[] A, int target) {// 定义左右指针int i = 0, j = A.length - 1;// 定义循环条件while (i <= j) {// 定义中间指针mint m = (i + j) / 2;// 判断A[m] 值 与 target值if (target < A[m]) { j = m - 1;} else {i = m + 1;}}//返回 <= 索引值 最靠右的索引值结果return i - 1;} -
获取 >= target 最靠左的索引位置 , 代码如下:
public static int binarySearchLeftMost1(int[] A, int target) {// 定义左右指针int i = 0, j = A.length - 1;// 定义循环条件while (i <= j) {// 定义中间指针mint m = (i + j) / 2;// 判断A[m] 值 与 target值if (target <= A[m]) {// 中间值>= targetj = m - 1;} else {// 中间值小 : 指针[i , m]中的值都会比target值小i = m + 1;}}//返回 >= target最靠左的索引位置return i;}
应用
- leftMost() :
- 求排名 leftMost() + 1 ;
- 求前任 leftMost() - 1 ;
- rightMost() :
- 求后任 rightMost + 1;
- 最近邻居问题
- 求前任 , 求后任
- 计算两个值 离 本值 更小的
- 范围查询
- x < n : [0 , leftMost(n) - 1]
- x <= n : [0 , rightMost(n)]
- x > n : [rightMost(n) + 1 , ∞]
- x >= n : [leftMost(n) , ∞]
- n <= x <= m : [leftMost(n) , rightMost(m)]
- n < x < m : [rightMost(n) + 1 . leftMost(m) - 1]
性能
- 时间复杂度最坏情况 : O(log(n))
- 空间复杂度 : O(1)
数组
-
连续存储
- -> 故可以通过索引值计算地址
- 公式 : 索引位置 + i * 字节数
-
随机访问时间复杂度: O(1)
-
动态数组类需要三个东西
- 数组容量
- 数组逻辑大小 : 就是数组实际存了几个值
- 静态数组
-
给数组添加元素
-
在末尾添加元素 => 给数组size位置上添加元素 -> 即调用下面方法
-
给数组指定位置添加元素
- 将数组指定位置后的元素后移
- 插入元素到指定位置上
-
插入删除的时间复杂度: O(n)
-
代码如下:
// 给数组添加元素 => 给数组size位置上添加元素private void add(int element){ // arrs[size] = element; // size++;addAppoint(size, element);}// 给数组指定位置添加元素private void addAppoint(int index , int element){if (index >= 0 && index < size){System.arraycopy(arrs, index, arrs, index + 1, size - index);}arrs[index] = element;size++;}
-
-
当数组存储元素达到容量上限,需要考虑数组扩容问题
-
每次添加元素的时候,判断size和capacity
- 定义一个新数组,容量大小是旧数组的1.5倍或两倍
- 将旧数组的数据复制到新数组中
- 将新数组的引用值 赋值 给旧数组
-
使用懒惰初始化思想优化代码
-
代码如下:
private void checkArrsCapacity() {if (size == 0) {arrs = new int[capacity];} else if (capacity == size) {capacity += capacity >> 1; // 扩大数组容量int[] newArrs = new int[capacity];System.arraycopy(arrs, 0, newArrs, 0, size);arrs = newArrs;}}@Test@DisplayName("测试扩容")public void test5() {DynamicArray dynamicArray = new DynamicArray();for (int i = 0; i < 9; i++) {dynamicArray.add(i + 1);}assertIterableEquals(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9), dynamicArray);}
-
-
给动态数组遍历的三种方式
-
使用Consumer函数式接口,实现遍历
// 动态数组的遍历 , 使用Comsumer函数式接口实现public void foreach(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {consumer.accept(arrs[i]);}}@Testpublic void test3() {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(1);dynamicArray.add(2);dynamicArray.add(3);dynamicArray.foreach(System.out::println);} -
使用迭代器实现遍历
@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {int i = 0;@Overridepublic boolean hasNext() {return i < size;}@Overridepublic Integer next() {return arrs[i++];}};}@Testpublic void test2() {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(1);dynamicArray.add(2);dynamicArray.add(3);for (Integer element : dynamicArray) {System.out.println(element);}} -
使用stream流实现遍历
// 动态数组的遍历: 使用stream流实现public IntStream stream(){return IntStream.of(Arrays.copyOfRange(arrs, 0, size));}@Testpublic void test1() {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(1);dynamicArray.add(2);dynamicArray.add(3);dynamicArray.stream().forEach(System.out::println);}
-
-
动态数组的删除
- 使用system.arraycopy方法, 将要删除指针后的元素向前移动一位
- 插入删除: O(n)
public int remove(int index) {int removeNum = arrs[index]; // 返回删除数据if (index < size - 1) {System.arraycopy(arrs, index + 1, arrs, index, size - index - 1);}size--;return removeNum;}// 使用断言进行测试@Test@DisplayName("测试删除")public void test4() {DynamicArray dynamicArray = new DynamicArray();dynamicArray.add(1);dynamicArray.add(2);dynamicArray.add(3);dynamicArray.add(4);dynamicArray.add(5);int remove = dynamicArray.remove(3); // System.out.println("remove = " + remove);assertEquals(4 , remove);// 遍历剩余数组元素// dynamicArray.foreach(System.out::println);assertIterableEquals(List.of(1,2,3,5), dynamicArray);}