赞
踩
本道题是要在一个先升后降的数组查找拐点,如果我们采用暴力搜索的话,时间复杂度为O(n),但题目要求我们设计时间复杂度为O(logn)的算法,我们不难看出这道题也是具有二段性的,那么我们就可以采用二分查找。
-
- /**
- * 在山形数组中找到峰值的索引。
- * 山形数组是指一个数组,其中存在一个元素,它大于其前后的所有元素(即峰值),
- * 且该元素前后的元素递增或递减。
- *
- * @param arr 山形数组,不为空且长度至少为3。
- * @return 返回数组中峰值的索引。如果有多个峰值,返回任意一个即可。
- */
- public int peakIndexInMountainArray(int[] arr) {
- /* 初始化左右指针 */
- int left = 1, right = arr.length - 2;
- /* 使用二分查找法寻找峰值 */
- while (left < right) {
- /* 计算中间索引,避免整数溢出,并确保mid大于left */
- int mid = left + (right - left + 1) / 2;
- /* 如果中间元素大于其前一个元素,则峰值在mid或其右侧 */
- if (arr[mid] > arr[mid - 1]) {
- left = mid;
- } else {
- /* 否则,峰值在mid或其左侧 */
- right = mid - 1;
- }
- }
- /* 当左右指针相遇时,即找到峰值 */
- return left;
- }
时间复杂度为O(logn),n为数组的长度,每次循环都会干掉一半的数据。
空间复杂度为O(1),只用了常数个变量。
以arr = [0,10,5,2]为例
第一步:初始化
left=1,right=2
第二步:查找峰顶
第三步:返回结果
此时left=1,将left返回即可。
本道题与前面的题目类似,在数组中存在多个峰值,只需要找到其中一个峰值即可。若使用暴力解法,时间复杂度为O(n),我们可以使用二分查找,来降低复杂度,通过二分,能让时间复杂度达到O(logn).
- /**
- * 寻找峰值元素的索引。
- * 峰值元素被定义为大于其邻居的元素。
- *
- * @param nums 整数数组,其中存在至少一个峰值元素
- * @return 返回峰值元素的索引
- */
- public int findPeakElement(int[] nums) {
- /* 初始化左右指针 */
- int left = 0;
- int right = nums.length - 1;
-
- /* 使用二分查找法寻找峰值 */
- while (left < right) {
- /* 计算中间索引,避免整数溢出 */
- int mid = left + (right - left) / 2;
-
- /* 如果中间元素大于其右侧元素,则峰值在左侧或就是中间元素 */
- if (nums[mid] > nums[mid + 1]) {
- right = mid;
- } else {
- /* 否则,峰值在右侧 */
- left = mid + 1;
- }
- }
-
- /* 当左右指针相遇时,即找到峰值 */
- return left;
- }
时间复杂度为O(logn),n为数组长度,在循环的过程中,每次都能排除掉一半的数据量。
空间复杂度为O(1),只用了常数个变量。
以nums=[1,2,1,3,5,6,4]
第一步:初始化
让left=0,right=6
第二步:查找峰值
2.mid=4+(6-4)/2=5,nums[mid]=6>nums[mid+1]=4,说明此时峰值在左区间,让right=mid。
3.mid=4+(5-4)/2=4,nums[mid]=5<nums[mid+1]=6,此时让left=mid+1,同时left和right相遇,说明此时找到了峰值.
第三步:返回结果
此时left=5,返回即可。
本道题是要在一个被旋转后的数组中找到最小的元素,采用暴力遍历的算法,时间复杂度能达到O(n),但题目要求我们设计O(logn)的算法,我们可以看得出本道题也是具有二段性的,可以看成两段升序的数组。
- /**
- * 在旋转后的有序数组中查找最小值。
- * 旋转有序数组是指原数组为非递减数组,将数组从某个位置分割成两部分,然后将两部分的顺序调换后形成的数组。
- * 例如,原数组[0,1,2,4,5,6,7]在数字4处旋转后变为[4,5,6,7,0,1,2]。
- * 此函数旨在在这种旋转后的数组中找到最小的数字。
- *
- * @param nums 旋转后的有序数组
- * @return 数组中的最小值
- */
- public int findMin(int[] nums) {
- int left = 0, right = nums.length - 1;
- // 如果数组的第一个元素小于最后一个元素,说明数组未旋转或旋转后的最小值就是第一个元素
- if (nums[left] < nums[right]) {
- return nums[left];
- }
- // 使用二分查找法寻找最小值
- while (left < right) {
- int mid = left + (right - left) / 2;
- // 如果中间位置的元素大于最右边的元素,说明最小值在mid右侧
- if (nums[mid] > nums[right]) {
- left = mid + 1;
- } else {
- // 否则,最小值在mid或其左侧
- right = mid;
- }
- }
- // 最终right指向最小值的位置
- return nums[right];
- }
时间复杂度为O(logn)
空间复杂度为O(1)
以nums = [4,5,6,7,0,1,2]为例
第一步:初始化
left=0,right=6
第二步:预处理
此时nums[left]=4>nums[right]=7,继续进行下续操作
第三步:找最小值
2.mid=4+(6-4)/2=5,nums[mid]=1<nums[right]=2,让right=mid=5
3.mid=4+(5-1)/2=4,nums[mid]=0<nums[right]=1,此时让right=mid,同时left和right相遇,结束循环。
第四步:返回结果
此时返回nums[left]=0即可。
本道题是要在一个从0~n-1的数组中找缺失的数,我们可以采用哈希表来解决,但此时时空复杂度达到了O(n),这是一个有序的数组,我们可以采用二分查找来解决,使时间复杂度达到O(logn).我们可以发现,每个数组的下标和其元素是相同的,那么我们可以通过判断下标和元素的大小,来确定缺失值的位置。
- /**
- * 记录出席情况的函数。
- * 通过数组记录每个人的出席情况,其中数组的索引代表人的编号,数组的值代表该人实际的出席编号。
- * 函数的目的是找到第一个未出席的人的编号。
- *
- * @param records 出席记录数组,数组的第i个元素表示第i个人的出席编号。
- * @return 返回第一个未出席的人的编号。如果所有人都出席了,则返回下一个应该出席的编号。
- */
- public int takeAttendance(int[] records) {
- /* 初始化左右指针 */
- int left = 0, right = records.length - 1;
- /* 使用二分查找法来寻找第一个未出席的人 */
- while (left < right) {
- /* 计算中间位置,避免整数溢出 */
- int mid = left + (right - left) / 2;
- /* 如果中间位置的人的出席编号等于其位置,则说明左边的人都出席了,调整左指针 */
- if (records[mid] == mid) {
- left = mid + 1;
- } else {
- /* 否则,说明中间位置的人未出席或者出席编号在左边,调整右指针 */
- right = mid;
- }
- }
- /* 检查最后一个人是否出席,如果出席则返回下一个出席编号,否则返回当前出席的最后一个编号 */
- return left == records[left] ? left + 1 : left;
- }
时间复杂度为O(logn),
空间复杂度为O(1)
records = [0,1,2,3,5]
第一步:初始化
left=0,right=4
第二步:查找缺失值
2.mid=3+(4-3)/2=3,records[mid]=3=mid,让left=mid+1,此时left=right,结束循环。
第三步:返回结果
此时判断records[left]是否等于left,但通过判断不是,所以这里直接返回left=4即可。
二分查找的算法专题就先到这里了~
若有不足,欢迎指正~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。