栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

面试题11:旋转数组的最小数字【Java实现】

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

面试题11:旋转数组的最小数字【Java实现】

题目

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素

输入:[3,4,5,1,2]		//这是[1,2,3,4,5]的一个旋转
输出:1		//该数组的最小值为1    
思路
  • 最简单的方式自然是进行遍历记录最小值,这种方式复杂度为O(n)。不过这种方法未利用到旋转数组的特性,因此还有改进空间。
  • 旋转本质上就是将原先完全递增的数组取部分子数组嫁接到原数组末尾【当旋转长度为0时即不进行旋转】
  • 我们注意到旋转之后的数组实际上可以划分为两个排序的子数组,而且前面子数组的元素都大于等于后面子数组的元素,同时最小的元素正好是两个子数组的分界线,我们以此为基础进行二分查找。
  • 令mid=(left+right)/2
    • 当arr[mid]>=arr[left]时,说明mid此时指向的位置属于第一个子数组,最小值肯定在mid处或后边,此时令left=mid,缩小查找范围;
    • 当arr[mid]<=arr[right]时,说明mid此时指向的位置属于第二个子数组,最小值肯定在mid处或前边,此时令right=mid,缩小查找范围;
    • 当right-left==1时,说明此时left指向了第一个子数组的最大值,right指向了第二个子数组的最小值,此时right指向的数值就是我们要找的最小值
  • 还有一种特殊情况需要进行考虑,即arr[left]==arr[right]&&arr[left]==arr[mid],此时我们无法辨别mid指向的元素是属于第一个子数组还是第二个子数组,因此无法缩小范围,这种情况下只能使用顺序查找。
代码实现
	public static int minNum(int arr[]) {
		// 左右下标
		int left = 0, right = arr.length - 1;
		int mid = left; // 中间位置下标
		while (arr[left] >= arr[right]) {
			if (right - left == 1) {
				// 说明此时右指针指向最小数
				mid = right;
				break;
			}
			mid = (left + right) / 2; // 确立中间位置下标
			if (arr[left] == arr[right] && arr[left] == arr[mid]) {
				// 若三个下标指向的数字都相等
				// 此时无法判断中间数值是属于第一个子数组还是第二个子数组
				// 因此此时无法使用二分,只能顺序查找
				return minInOrder(arr, left, right);
			}
			if (arr[mid] >= arr[left]) {
				left = mid;
			}
			if (arr[mid] <= arr[right]) {
				right = mid;
			}
		}
		//当旋转长度为0时,数组的第一个元素一定是最小值
		return arr[mid];
	}
	//顺序查找最小值
	public static int minInOrder(int arr[], int left, int right) {
		int result = arr[left];
		for (int i = left + 1; i < right; i++) {
			result = Math.min(result, arr[i]);
		}
		return result;
	}

题目来源于《剑指Offer:名企面试官精讲经典编程题》

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948876.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号