🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:
🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm=1001.2014.3001.5482
🍕 Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(96平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
🍃 Spring(97平均质量分)https://blog.csdn.net/2301_80050796/category_12724152.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~
目录
- 5. 山峰数组的峰顶(难度:🟢1度)
- 6. 搜索旋转排序数组中的最小值(难度:🔵2度)
- 7. 点名(难度:🟢1度)
- 8. 寻找峰值(难度🔵2度)
5. 山峰数组的峰顶(难度:🟢1度)
OJ链接
- 题目描述
给定一个长度为 n 的整数 山脉 数组 arr ，其中的值递增到一个 峰值元素 然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1：
输入：arr = [0,1,0]
输出：1
示例 2：
输入：arr = [0,2,1,0]
输出：1
示例 3：
输入：arr = [0,10,5,2]
输出：1
- 算法原理
- 分析峰顶位置的数据特点，以及山峰两旁的数据的特点：
◦ 峰顶数据特点：arr[i] > arr[i - 1] && arr[i] > arr[i + 1] ；
◦ 峰顶左边的数据特点：arr[i] > arr[i - 1] && arr[i] < arr[i + 1]，也就是呈现上升趋势；
◦ 峰顶右边数据的特点： arr[i] < arr[i - 1] && arr[i] > arr[i + 1] ，也就是呈现下降趋势。 - 因此，根据mid 位置的信息，我们可以分为下⾯三种情况：
◦ 如果mid 位置呈现上升趋势，说明我们接下来要在[mid + 1, right] 区间继续搜索；
◦ 如果mid 位置呈现下降趋势，说明我们接下来要在[left, mid - 1] 区间搜索；
◦ 如果mid 位置就是山峰，直接返回结果。
[细节问题] 由于两个山脚一定不是山顶,所以直接从第二个和倒数第二个元素开始.
- 代码实现
class Solution {public int peakIndexInMountainArray(int[] arr) {int left = 1;int right = arr.length-2;while(left < right){int mid = left + (right - left + 1)/2;if (arr[mid-1] < arr[mid]){left = mid;}else{right = mid - 1;}}return left;}
}
这道题需要注意的地方是,如果使用向下取整,在条件判断的时候,只能使用arr[mid-1] < arr[mid],不可以使用arr[i] < arr[i + 1],因为在取值的时候,很可能正好取到峰值,这时候left不会更新,right也会更新到mid的前一个值,此时返回值就不准确.
6. 搜索旋转排序数组中的最小值(难度:🔵2度)
- 题目描述
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
- 算法原理
其中C 点就是我们要求的点。
二分的本质：找到⼀个判断标准，使得查找区间能够⼀分为二。以D点作为分界点.
通过图像我们可以发现，[A，B] 区间内的点都是严格大于D点的值的，[C,D]区间内的值是小于等于D点的值的.
因此，初始化左右两个指针left ， right ：
然后根据mid 的落点，我们可以这样划分下⼀次查询的区间：
▪ 当mid 在[A，B] 区间的时候，也就是mid 位置的值严格大于D 点的值，下⼀次查询区间在[mid + 1，right] 上；
▪ 当mid 在[C，D] 区间的时候，也就是mid 位置的值严格小于等于D 点的值，下次查询区间在[left，mid] 上。
当区间长度变成1 的时候，就是我们要找的结果 - 代码实现
class Solution {public int findMin(int[] nums) {int left = 0;int right = nums.length - 1;int x = nums[right];while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] > x) {left = mid + 1;} else {right = mid;}}return nums[right];}
}
[注意] 本题如果以D为分界点的话,只能使用向上取整,因为[A,B]区间都是大于D的,没有等于的地方.
7. 点名(难度:🟢1度)
- 题目描述
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
示例 1:
输入: records = [0,1,2,3,5]
输出: 4
示例 2:
输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7
- 算法原理
本题只讲解⼀个最优的⼆分法，来解决这个问题。
在这个升序的数组中，我们发现：
▪ 在第⼀个缺失位置的左边，数组内的元素都是与数组的下标相等的；
▪ 在第⼀个缺失位置的右边，数组内的元素与数组下标是不相等的。
因此，我们可以利用这个「⼆段性」，来使用「⼆分查找」算法
这道题最重要的是找到下标与数据的关系,才比较容易看出这道题的二段性. - 代码实现
class Solution {public int takeAttendance(int[] records) {int left = 0;int right = records.length - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (mid == records[mid]) {left = mid;} else {right = mid - 1;}}if (records[left] == left) {return left + 1;}return left;}
}
8. 寻找峰值(难度🔵2度)
- 题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
- 算法原理
这道题与第5题的不同就是,这道题就是一个普通的数组中寻找最大值,而第5题是在一个山峰数组中寻找最大值,也就是说这道题有可能取到0,和最后一个位置的值.其他与第五题完全相同. - 代码实现
class Solution {public int findPeakElement(int[] nums) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (nums[mid - 1] < nums[mid]) {left = mid;} else {right = mid - 1;}}return left;}
}
