优质东莞网站制作公司,thinkphp网站源码下载,wordpress顺风车源码,注册公司需要多久的时间数字在排序数组中出现次数
题目#xff1a;统计一个数字在一个排序数组中出现的次数。例如#xff0c;输入数组{1,2#xff0c;3#xff0c;3,3#xff0c;3,3#xff0c;4,5} 和数字3#xff0c;由于3 在数组中出现的次数是5#xff0c;因此返回5
简单方案一
既然输…数字在排序数组中出现次数
题目统计一个数字在一个排序数组中出现的次数。例如输入数组{1,233,33,34,5} 和数字3由于3 在数组中出现的次数是5因此返回5
简单方案一
既然输入的数组是有序的那么最简单的方式是一次遍历统计出需要的数字出现的个数时间复杂度是O(n)实现方法如下
*** 查询有序数组中数字k 出现的次数** author liaojiamin* Date:Created in 16:08 2021/6/24*/
public class GetNumberOfK {public static void main(String[] args) {int[] array new int[]{1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 33, 44, 55, 56, 56, 56, 56, 56, 57};System.out.println(countK(array, 0));}/*** 方法一遍历统计 O(n)*/public static Integer countK(int[] array, int k) {if (array null || array.length 0) {return -1;}int count 0;for (int i 0; i array.length; i) {if (array[i] k) {count;}}return count;}}方法二二分查找
有序数组而且是查询那么时间效率最高的就是二分查找了分析流程如下 如上案例中二分查找找出其中一个3 的位置标记为position此时可能前后都还存在3那么从position向前遍历查找之前的3得到firstK从position向后遍历查找之后的3得到lastK那么k出现的次数n lastK - firstK 1 如上分析有如下代码
/*** 查询有序数组中数字k 出现的次数** author liaojiamin* Date:Created in 16:08 2021/6/24*/
public class GetNumberOfK {public static void main(String[] args) {int[] array new int[]{1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 33, 44, 55, 56, 56, 56, 56, 56, 57};System.out.println(binarySearchK(array, 0));}/*** 方法二二分查找找出k得到k后左右遍历k直到找到firstK和lastK* O(n)*/public static Integer binarySearchK(int[] array, int k) {Integer positionK binarySearch(array, 0, array.length - 1, k);if (positionK 0) {return -1;}Integer firstK positionK;Integer lastK positionK;for (int i positionK; i array.length; i) {if (array[i] k) {lastK i;}}for (int i positionK; i 0; i--) {if (array[i] k) {firstK i;}}return lastK - firstK 1;}public static Integer binarySearch(int[] array, int left, int right, int k) {if (array null || left 0 || right array.length - 1 || left right) {return -1;}int middle (left right) / 2;if (array[middle] k) {return middle;}if (array[middle] k) {return binarySearch(array, left, middle - 1, k);}if (array[middle] k) {return binarySearch(array, middle 1, right, k);}return -1;}
}如上算法因为k出现的次数可能是n次那么我们向前向后遍历的次数可能就是n 那么时间复杂度还是O(n)并没有达到优化的目的。此算法中实际主要消耗在如何确定重复数字的第一个k与最后一个k的位置上。
方案三纯二分查找 方案二中既然可以通过二分查找找到其中一个3 那么我们是否能通过二分查找找到firstK和lastK 分析如下 先查找第一个k 标记位置为position当地position-1 个位置的值也是k的时候我们认为k之前还有重复的数字k存在依然用二分查找继续找 left ~ k-1 位置中的k持续以上步骤直到position-1 位置不是k为止我们得到firstK position同理如果position1位置也是k那么我们递归position1 ~ right的数组中二分查找k得到lastK如上我们用纯二分查找的方式找出了lastKfirstK 经如上分析有如下代码
/*** 查询有序数组中数字k 出现的次数** author liaojiamin* Date:Created in 16:08 2021/6/24*/
public class GetNumberOfK {public static void main(String[] args) {int[] array new int[]{1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 33, 44, 55, 56, 56, 56, 56, 56, 57};System.out.println(binarySearchAllK(array, 0));}/*** 方法三还是二分查找分别找出firstK lastK*/public static Integer binarySearchAllK(int[] array, int k) {if (array null || array.length 0) {return -1;}int firstK binarySearchFirstK(array, 0, array.length - 1, k);int lastK binarySearchLastK(array, 0, array.length - 1, k);if (firstK 0 lastK 0) {return -1;}return lastK - firstK 1;}/*** 二分查找第一个k*/public static Integer binarySearchFirstK(int[] array, int left, int right, int k) {if (array null || left 0 || right array.length - 1 || left right) {return -1;}int middle (left right) / 2;if (array[middle] k) {if (middle - 1 left array[middle - 1] k) {return binarySearchFirstK(array, left, middle - 1, k);} else {return middle;}}if (array[middle] k) {return binarySearchFirstK(array, middle 1, right, k);}if (array[middle] k) {return binarySearchFirstK(array, left, middle - 1, k);}return -1;}/*** 二分查找最后一个k*/public static Integer binarySearchLastK(int[] array, int left, int right, int k) {if (array null || left 0 || right array.length - 1 || left right) {return -1;}int middle (left right) / 2;if (array[middle] k) {if (middle 1 right array[middle 1] k) {return binarySearchLastK(array, middle 1, right, k);} else {return middle;}}if (array[middle] k) {return binarySearchLastK(array, left, middle - 1, k);}if (array[middle] k) {return binarySearchLastK(array, middle 1, right, k);}return -1;}
}如上实现中firstKlastK都是使用二分查找在数组中查找并且二分查找的总量不会大于整个数组的量n他们两次查询的时间复杂度都是O(logn)因此总的时间复杂度就是O(logn)达到了我们优化的目的。
上一篇数据结构与算法–最小的k个数 下一篇数据结构与算法–二叉树的深度问题
