通知
此博客运行在jpress系统上,如果你喜欢此博客模板,请加QQ群:1061691290(whimurmur模板/jpress插件),免费下载使用

leetcode探索之二分查找学习 模板 II

859人浏览 / 0人评论 | 作者:whisper  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode  | 

作者:whisper

链接:http://proprogrammar.com:443/article/626

声明:请尊重原作者的劳动,如需转载请注明出处


    本章展示了模板 #2 的代码片段。它简要说明了何时使用该模板,并强调了这 3 个模板之间的关键语法差异。

    二分查找模板 II

int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;

  int left = 0, right = nums.length;
  while(left < right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }
    else { right = mid; }
  }

  // Post-processing:
  // End Condition: left == right
  if(left != nums.length && nums[left] == target) return left;
  return -1;
}

    模板 #2 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。

    关键属性

  • 一种实现二分查找的高级方法。
  • 查找条件需要访问元素的直接右邻居。
  • 使用元素的右邻居来确定是否满足条件,并决定是向左还是向右。
  • 保证查找空间在每一步中至少有 2 个元素。
  • 需要进行后处理。 当你剩下 1 个元素时,循环 / 递归结束。 需要评估剩余元素是否符合条件。

    区分语法

  • 初始条件:left = 0, right = length
  • 终止:left == right
  • 向左查找:right = mid
  • 向右查找:left = mid+1

    算法-第一个错误的版本

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5,并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。
/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

    public class Solution extends VersionControl {
    // 折半查找,存上一个错误版本,如果当前版本是正确版本,且比错误版本小1,那么那个错误版本是第一个错误版本
    // 坑爹的不能用int,会超出范围,要用long
    // 左侧是goodVersion,右侧是badVersion,只可能会在右侧而不会在左侧,这是这个二分查找模板的精华
    public int firstBadVersion(int n) {
        long goodVersion = -1;
        long badVersion = n;
        long temp;
        
        if(isBadVersion(1)){
            return 1;
        }else{
            goodVersion = 1;   
        }
        
        while(badVersion != goodVersion + 1){
            temp = (goodVersion + badVersion) / 2;
            if(isBadVersion((int)temp)){
                badVersion = temp;
            }else{
                goodVersion = temp;
            }
        }
        
        return (int)badVersion;
    }
}

    解释在注释中

    算法-寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[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。

说明:

你的解法应该是 O(logN) 时间复杂度的。

class Solution {
    public int findPeakElement(int[] nums) {
        if(nums == null || nums.length == 0){
            return -1;
        }else if(nums.length == 1){
            return 0;
        }
        
        int i = 0;
        while(++i < nums.length){
            if(nums[i-1] > nums[i]){
                return i-1;
            }
        }
        
        return nums.length - 1;
    }
}

    自己写的,代码很短,但复杂度是O(n)的,再看一种解法

class Solution {
    public int findPeakElement(int[] nums) {
         int imin = 0;
        int imax = nums.length-1;
        int pa = (imax-imin)/2;
        if(imax == 1) {
        	if(nums[0] > nums[1]) {
        		return 0;
        	}else {
        		return 1;
        	}
        }else if(imax == 0){
            return 0;
        }else{
            int L1 = F1(nums,imin,pa);
            int R1 = F1(nums,pa+1,imax);
            if(L1 != -1) {
            	return L1;
            }
            if(R1 != -1) {
            	return R1;
            }
        }
        return -1;
    }
	public int F1(int[] nums,int a,int b) {
		if((b-a) == 0) {//剩1个
			if(a!=0 && b!= nums.length-1){
				if(nums[a]>nums[a-1] && nums[a]>nums[b+1]) {
		            return a;
				}
	        }
            if(a==0) {
	        	if(nums[0]>nums[1]) {
	        		return 0;
	        	}
	        }
            if(b==nums.length-1){
	        	if(nums[b]>nums[b-1]) {
	        		return b;
	        	}
	        }
		}else if((b-a)==1) {//剩2个
			if(a!=0) {//左边不是边界
				if(nums[a]>nums[a-1] && nums[a]>nums[a+1]){
		            return a;
		        }
			}
			if(b!=nums.length-1) {//右边不是边界
				if(nums[b]>nums[b-1] && nums[b]>nums[b+1]){
		            return b;
		        }
			}
			if(a==0) {
				if(nums[0]>nums[1]) {
	        		return 0;
	        	}
			}
			if(b==nums.length-1) {
				if(nums[b]>nums[b-1]) {
	        		return b;
	        	}
			}
		}else{
			int pb = (a+b)/2;
			int L1 = F1(nums,a,pb);
            int R1 = F1(nums,pb+1,b);
            if(L1 != -1) {
            	return L1;
            }
            if(R1 != -1) {
            	return R1;
            }
		}
		return -1;
	}
}

    这个是不断把长度从中间分两段,分别计算两段的情况,是递归分治的方法,代码写的很长,但复杂度是O(logn)的

    算法-寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0
class Solution {
    // 想法:去除掉最小值在开始在末尾的情况,那在中间一定存在当前数比上一个数小的情况,此时当前的数即最小的数
    public int findMin(int[] nums) {
        if(nums == null || nums.length == 0){
            return -1;
        }else if(nums.length == 1 || nums[0] < nums[nums.length - 1]){//最小值在开始处
            return nums[0];
        }else if(nums[nums.length - 1] < nums[nums.length - 2]){//最小值在末尾处
            return nums[nums.length - 1];
        }
        
        int left = 0, right = nums.length - 1, mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(mid == 0){//不会在开始
                left++;
            }else if(mid == nums.length - 1){//不会在结尾
                right--;
            }else if(nums[mid] > nums[mid - 1]){
                if(nums[mid] > nums[0]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }else{
                return nums[mid];
            }
        }
        
        return -1;
    }
}

    这与上一篇文章模板I中搜索旋转排序数组有些类似,解析在注释里,再看另一种解法

class Solution {
    // right部分是可能取值,left部分是不可能取值
    public int findMin(int[] nums) {
        int left = -1, right = nums.length - 1, mid;

        while (left < right) {

            mid = (left + right) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                return nums[mid];
            }
        }
        return nums[right];
    }
}

    这里用的思法是模板II的思想,但不容易想到


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!