欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
山脉数组的顶峰索引
解法
小细节:根据题目特性,山脉数组的第一个数和最后一个数一定不是峰值
暴力枚举O(n):按顺序遍历,当遇到一个数x比后面的数大时,返回x的索引
解法二: 二分查找算法 ,利用山脉数组的二段性,将数组分为arr[i] > arr[i - 1]和arr[i] < arr[i - 1]两部分
画图举例
代码
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 1, right = arr.length - 2;
while(left < right){
int mid = left + (right - left + 1) / 2;
if(arr[mid] > arr[mid - 1]) left = mid;
else right = mid - 1;
}
return left;
}
}寻找峰值
解法
根据题目得出可能有多个,得出一个就行,所以我们可以选择求数组 出现的第一个峰值
暴力解法O(n): 从第一个位置开始遍历,一直走,分情况讨论,分三种
- 第一个数最大,往后走 数逐渐减小
- 数先上升再下降,下降的前一个数为峰值
- 数一直上升,最后一个数为峰值
解法二: 二分查找算法, 利用二段性,分两种情况
数组开始呈下降趋势,即arr[mid] > arr[mid + 1], 得出峰值在左边区间,right = mid
数组开始呈上升趋势,即arr[mid] < arr[mid + 1], 峰值在右边区间,left = mid + 1
画图举例
代码
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, 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(n): 从前往后遍历数组找到最小值
解法二: 利用二段性将数组分为两段,AB段和CD段,都是呈上升趋势,且CD段最后一个值(标记为 x )小于AB段的值,所以找最小值 要到CD段里找.
当arr[mid] > x,说明此时mid在AB段,更新left= mid+ 1;
当arr[mid] < x,说明此时mid在CD段,更新right= mid;
画图举例
代码
class Solution {
public int findMin(int[] nums) {
int left = 0, 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[left];
}
}点名
解法
解法有很多种:1.利用哈希表 , 2.直接遍历找结果 3.位运算,异或,将题给数组与完整数组异或
4.等差求和,求出完整数组的和,再减去题给的数组的和,得出的就是缺失的数 . 上面的这4种解法时间复杂度都是O(n)
二分查找算法:找出数组的二段性,左边区间数组的值等于下标,右边区间不等于,找出第一个不等于数组值的下标即可
- 左区间: nums[mid] == mid 更新left = mid + 1;
- 右区间: nums[mid] != mid 更新 right = mid;
细节处理:当题给的数组是一个 完全递增的数组,缺的数是left+1
画图举例
代码
class Solution {
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;
}
if(left == records[left]) return left + 1;
return left;
}
}