问题1
旋转数组最小数
原理
- 这类问题的本质是使用二分法，因为遍历的效率是O(n),二分的时间复杂度为log(n)。
- 二分之后，一半是有序一半是无序，最小值就隐藏在无序数组的一层。多次二分就可以找到最小值。
代码
class Solution {
public int findMin(int[] nums) {
int low = 0;
int high = nums.length-1;
while (low<high){
int mid = low+(high-low)/2;
if(nums[mid]>nums[high]){
low = mid+1;
}else{
high = mid;
}
}
return nums[low];
}
}
注意事项
- 只要抓住，最小的元素肯定在无序的一侧就迎刃而解了。
- 注意元素不能重复，重复的情况就不太一样了。
问题2
旋转数组最小数，包含重复数
原理
- 首先，考虑的还是二分查找。
- 其次，需要注意的是如果元素重复的情况，例如：1，2，2，2，2，2，2 这种情况原来的办法就不好使了，这个时候我们需要处理的是当nums[mid]==nums[high]的情况，high--就可以完美处理这个问题
- 最后，一定要考虑重复的情况。
代码
class Solution {
public int findMin(int[] nums) {
int low = 0;
int high = nums.length-1;
while (low<high){
int mid = low+(high-low)/2;
if(nums[mid]>nums[high]){
low = mid+1;
}else if(nums[mid]>nums[high]){
high = mid;
}else{
high--;
}
}
return nums[low];
}
}
注意事项
- 考虑重复元素的处理high--
问题3
旋转数组寻找目标数
原理
- 本质上还是二分查找
- 情况一，nums[mid]==target 直接返回
- 情况二，nums[mid]<nums[high] 说明右半侧有序，直接找target在右半侧的位置
- 情况三，nums[mid]>nums[high]说明左半侧有序，直接找target在左半侧的位置
代码
class Solution {
public int search(int[] nums, int target) {
int low = 0;
int high = nums.length-1;
while (low<=high){
int mid = low+(high-low)/2;
if (nums[mid]==target){
return mid;
}
// 右半边有序
if (nums[mid]<nums[high]){
if(nums[mid]<target&&target<=nums[high]){
low = mid+1;
}else{
high = mid-1;
}
}else{
if (nums[low]<=target&&target<nums[mid]){
high = mid-1;
}else{
low = mid+1;
}
}
}
return -1;
}
}
注意事项
- 注意low<=high 可以取到==
- 注意元素不能重复，重复的情况需要考虑问题4
问题4
旋转数组寻找目标数，包含重复数
原理
- 本质上还是二分查找
- 情况一，nums[mid]==target 直接返回
- 情况二，nums[mid]<nums[high] 说明右半侧有序，直接找target在右半侧的位置
- 情况三，nums[mid]>nums[high]说明左半侧有序，直接找target在左半侧的位置
- 情况四，nums[mid]==nums[high],high--
代码
class Solution {
public boolean search(int[] nums, int target) {
int low = 0;
int high = nums.length-1;
while (low<=high){
int mid = low +(high-low)/2;
if(nums[mid]==target){
return true;
}
if (nums[mid]<nums[high]){
if (nums[mid]<target&&target<=nums[high]){
low = mid+1;
}else{
high = mid-1;
}
}else if(nums[mid]>nums[high]){
if (nums[low]<=target&&target<nums[mid]){
high = mid-1;
}else{
low = mid+1;
}
}else {
high--;
}
}
return false;
}
}
注意事项
- 原理和问题3一样，注意的点和问题2一样，需要考虑重复元素的情况，重复元素的情况high--
问题5
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置
原理
- 首先这个问题还是一个二分查找的问题，只不过这个问题是需要查找两个元素而已。
- 可以实现两个函数一个findleft，一个findright
- 和普通的二分查找的区别在于，查找的过程可能存在重复的目标元素，我们的目标是找到重复元素的minLeft 或者maxRight。
代码
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = binaryLeft(nums,target);
if (left==-1){
return new int[]{-1,-1};
}
int right = binaryRight(nums,target);
return new int[]{left,right};
}
private int binaryLeft(int[] nums,int target){
int low = 0;
int high = nums.length-1;
while (low<=high){
int mid = low +(high-low)/2;
if (nums[mid]<target){
low = mid+1;
}else if(nums[mid]>target){
high = mid-1;
}else if(nums[mid]==target){
high = mid-1;
}
}
if (low != nums.length && nums[low] == target) {
return low;
}
return -1;
}
private int binaryRight(int[] nums,int target){
int low = 0;
int high = nums.length-1;
while (low<=high){
int mid = low +(high-low)/2;
if (nums[mid]<target){
low = mid+1;
}else if(nums[mid]>target){
high = mid-1;
}else if(nums[mid]==target){
low = mid+1;
}
}
return high;
}
}
注意事项
- 需要分成找left和right两种情况，最好利用两个函数实现。
- 需要考虑各种边界
- 第一当只有一个元素的时候例如：{1}的时候；
- 第二需要考虑 找到和找不到的情况，如何判断找到呢？low!=nums.length&&nums[low]==target 说明找到了。
- 第三需要注意的是，如果left找不到那么right就不用找了的特殊情况
问题6
两个有序数组找中位数
原理
代码
