剑指offer面试题8 旋转数组的最小数字

这篇具有很好参考价值的文章主要介绍了剑指offer面试题8 旋转数组的最小数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

考察点

算法二分搜索

知识点

二分搜索算法是针对排序的数组,先找到中间元素,如果待查找元素比中间元素大,说明待查
找元素肯定不在左边那片区域内,如果待查找元素比中间元素小,说明待查找元素肯定不在右
边那片区域内,反复进行该过程直到找到元素为止对于搜索而言,降低复杂度的唯一方式就是
每一次轮询以后能缩小搜索范围或者过滤掉更多的不可能元素,我们最普通的遍历数组的方式
,每轮询完一次只能过滤掉一个元素。而二分搜索每轮询完一次可以过滤掉一半的元素,因此
这就是它非常高效的原因(log(n))

题目

分析
首先一定要记住只要看到排序数组的查找,思维一定要往二分法上靠,然后再思考清楚如何利用二分法。而如何利用二分法一定要仔细分析所给的数组的特点:递增数组且最开始的若干元素搬到数组的末尾,相当于该数组由俩个递增小数组构成,前面的数组元素肯定大于等于后面的数组元素,且最小值肯定是第二个小数组的第一个元素。二分法需要首尾俩个指针以及中间元素,可以肯定的是如果中间元素比最左边的值大那说明最小值肯定在右边(左边的小递增数组特性),如果中间元素比最右边的值小那说明最小值肯定在左边(右边的小递增数组特性),到这一步的时候就需要拿数字举例一下看到底应该怎么找到最小值,最终举例完以后会发现按照上面的思路最终左边的指针和右边的指针相差1的时候,右边的指针指向的就是最小的元素(在解题没有思路的时候拿实际数据算一下然后找出其中的规律,我们的算法说白了就是把这个规律用程序表达出来)。最后考虑一些异常的情况:中间元素比最左边的值大的时候最小值肯定在右边吗?不一定,考虑数组{1,0,1,1,1}的情况,因此当最左边元素和中间元素以及最右边元素值相同的时候,就不能再使用二分法进行查找了
(末尾附上二分查找代码)文章来源地址https://www.toymoban.com/news/detail-820916.html

public class Eight {
	public static void main(String[] args) {
		int[] arr = {3,4,5,1,2};
		System.out.println(findMin(arr));
		int[] brr = {1,0,1,1,1};
		System.out.println(findMin(brr));
		int[] crr = {1,1,1,0,1};
		System.out.println(findMin(crr));
		int[] drr = {5,4,3,2,1};
		System.out.println(findMin(drr));
	}
	public static int findMin(int[] arr) {
		if (arr.length <= 0) {
			throw new Error("input error");
		}
		int start = 0;
		int end = arr.length - 1;
		if (arr[start] < arr[end]) {
			return arr[start];
		}
		while(arr[start] >= arr[end]) {
			if (start + 1 == end) {
				return arr[end];
			}
			int mid = (start + end) / 2;
			if (arr[start] == arr[mid] && arr[end] == arr[mid]) {
				int val = arr[start];
				for (int idx = start + 1;idx <= end;idx++) {
					if (val > arr[idx]) {
						val = arr[idx];
					}
				}
				return val;
			}
			if (arr[mid] >= arr[start]) {
				start = mid;
			} else if (arr[mid] <= arr[end]) {
				end = mid;
			} else {
				break;
			}
		}
		throw new Error("input error");
	}
}
//附上二分法查找
public class Erfen {
	public static void main(String[] args) {
		int[] arr = {1,2,3,4,11,17,18};
		System.out.println(erfen(arr,12));
		System.out.println(erfen(arr,18));
		System.out.println(erfen(arr,1));
		System.out.println(erfen(arr,11));

	}
	public static int erfen(int[] arr,int val) {
		int start = 0;
		int end = arr.length - 1;
		while(start <= end) {
			int mid = (start + end) / 2;
			if (arr[mid] == val) {
				return mid;
			} else if (arr[mid] < val) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		return -1;
	}
}

到了这里,关于剑指offer面试题8 旋转数组的最小数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剑指offer(C++)-JZ56:数组中只出现一次的两个数字(算法-位运算)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 数据范围:数组长度2≤n≤1000,数组中每个数

    2024年02月10日
    浏览(50)
  • 剑指offer45 把数组排成最小的数

    链接 其实这道题,大概看完就知道是一个排序的问题,无非就是数组中的元素以一个合适的位置排好序,这样从头加到尾,组成的整体数字最小!(题目中也暗示你排序问题了) 个人捉摸了一会,这道题能很好地锻炼仿函数的编写规则和库函数sort()的配套使用,还有就是巧妙地

    2024年01月16日
    浏览(42)
  • Java旋转数组中的最小数字(图文详解版)

    目录 1.题目描述 2.题解 分析 具体实现 方法一(遍历): 方法二(排序): 方法三(二分查找): 有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样

    2024年02月13日
    浏览(36)
  • 【剑指offer】数组中重复的数字

    👑专栏内容:力扣刷题 ⛪个人主页:子夜的星的主页 💕座右铭:前路未远,步履不停 剑指offer:数组中重复的数字 在一个长度为 n 的数组里的所有数字都在 0 0 0 到 n − 1 n-1 n − 1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复,也不知道每个数字重复了几

    2024年01月20日
    浏览(50)
  • (排序) 剑指 Offer 45. 把数组排成最小的数 ——【Leetcode每日一题】

    难度:中等 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 提示 : 0 nums.length = 100 说明: 输出结果可能非常大,所以你需要返回一个字符串而不

    2024年02月10日
    浏览(51)
  • 剑指offer03.数组中重复的数字

    看到这道题的第一眼想到的是先给它排序,然后双指针从左往右遍历,写了一个冒泡排序,但是我想到了应该会超时,因为冒泡时间复杂度是n的平方,输入大小时10000,肯定会超时,然后右又看了一下题目看到数字都是0-n-1,灵感一下子就来了,我先创建一个等大的自然数数

    2024年02月11日
    浏览(40)
  • 剑指 Offer 03. 数组中重复的数字

    剑指 Offer 03. 数组中重复的数字 利用题目的限制条件: 所有数字都在 0~n-1 的范围内 通过交互让数字和下标一一对应,如果有多个数字对应同一个下标,那就找到了答案。 另一种写法

    2024年02月11日
    浏览(36)
  • 【剑指offer|1.数组中重复的数字】

    : 长度为n的数组nums中所有数字都在0~n-1范围内 返回任意一个重复的数字 总体时间复杂度和空间复杂度分析: 修改数组的方法: 因为有n个元素,每一个元素都在0~(n-1)范围内,如果元素不重复的话, 对数组重排之后,下标和元素值之间应该是一一对应的关系 但是因为

    2023年04月22日
    浏览(38)
  • 剑指 Offer 45. !!把数组排成最小的数(使用比较器的定制排序;快速排序)

    剑指 Offer 45. 把数组排成最小的数 中等 662 相关企业 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 这道题在左程云算法课上讲过,但是这次

    2024年02月14日
    浏览(44)
  • 剑指offer39.数组中出现次数超过一半的数字

    这个题非常简单,解法有很多种,我用的是HashMap记录每个元素出现的次数,只要次数大于数组长度的一半就返回。下面是我的代码: 题解还有一种更牛逼的解法,把数组排序,然后返回数组中间的那个数就行,因为如果这个数出现的次数大于数组长度的一半的话,排完序后

    2024年02月13日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包