通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

二分法中分别获取high, low, mid的场景

12109人浏览 / 1人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  | 

作者:因情语写

链接:https://proprogrammar.com/article/379

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


    最近在做leetcode题的过程中多次用到了二分法,用到了分别获取high, low, mid值的方法,觉得应该写一篇文章记录一下。下面分别说一下。

    注:right, left; high, low; h, l都是一个意思,表示搜索的右端和左端(高端和低端),我以high, low, mid为例

    先分享一下原题

    33. 搜索旋转排序数组   要求的结果是mid

    5111. 分享巧克力    要求的结果是high

    475. 供暖器     要求的结果是low


    搜索旋转排序数组

    算法描述

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

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

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

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

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

    算法代码

    // 想法:用二分查找,数组分二段,两段分别递增,第一段值都比第二段大
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        while(right >= left){
            mid = (right + left) / 2;
            if(nums[mid] > target){
                // 目标值,中间值都在第一段
                if(target >= nums[0]){
                    right = mid - 1;
                // 目标值在第二段,中间值在第一段
                }else if(nums[mid] >= nums[0]){
                    left = mid + 1;
                // 目标值,中间值都在第二段
                }else{
                    right = mid - 1;
                }
            }else if(nums[mid] < target){
                // 目标值,中间值都在第一段
                if(nums[mid] >= nums[0]){
                    left = mid + 1;
                // 目标值在第一段,中间值在第二段
                }else if(target >= nums[0]){
                    right = mid - 1;
                // 目标值,中间值都在第二段
                }else{
                    left = mid + 1;
                }
            }else{
                return mid;
            }
        }
        
        return -1;
    }

    算法说明

    算法要求的结果是数组中的一个数,所以正常情况下(这个数在数组中)会返回这个数的索引 mid(否则返回-1),这里是求数组中一个数的相关信息,而mid正是用来找这个数的,最后返回的也是mid,high, low, mid三者的判断、赋值情况是

判断

while(right >= left)

赋值

mid = (right + left) / 2

right = mid - 1;

left = mid + 1;

mid是要求的值,right, left左右端点值

    分享巧克力

    算法描述

你有一大块巧克力,它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。

你打算和 K 名朋友一起分享这块巧克力,所以你需要将切割 K 次才能得到 K+1 块,每一块都由一些 连续 的小块组成。

为了表现出你的慷慨,你将会吃掉 总甜度最小 的一块,并将其余几块分给你的朋友们。

请找出一个最佳的切割策略,使得你所分得的巧克力 总甜度最大,并返回这个 最大总甜度

示例 1:

输入:sweetness = [1,2,3,4,5,6,7,8,9], K = 5
输出:6
解释:你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。

示例 2:

输入:sweetness = [5,6,7,8,9,1,2,3,4], K = 8
输出:1
解释:只有一种办法可以把巧克力分成 9 块。

示例 3:

输入:sweetness = [1,2,2,1,2,2,1,2,2], K = 2
输出:5
解释:你可以把巧克力分成 [1,2,2], [1,2,2], [1,2,2]。

提示:

  • 0 <= K < sweetness.length <= 10^4
  • 1 <= sweetness[i] <= 10^5

    算法代码

    // 二分法缩小范围
    public int maximizeSweetness(int[] sweetness, int K) {
        int low = 0, high = (int)1e9, mid, cont, temp;
        
        while(low < high) {
            // 二分法的一种取mid的方式
        	mid = (low + high + 1) / 2;
        	cont = 0;
        	temp = 0;
        	for(int i: sweetness) {
        		temp += i;
        		if(temp >= mid) {
        			temp = 0;
        			cont++;
        		}
        	}
        	
            // low值是满足条件的值
        	if(cont >= K + 1) {
        		low = mid;
        	}else {
        		high = mid - 1;
        	}
        }
        
        return low;
    }

    算法说明

    所要求值在high,low之间,不同切法都有总甜度,我们要求的是总甜度的最大值(最优解),怎么求呢,令满足要求的总甜度为low(开始最小,即要求最大,先设为最小,然后慢慢增大),然后慢慢增大low,直到不满足条件,从而得到满足条件的最大的low,high, low, mid三者的判断、赋值情况是

判断

while(low < high)

赋值

mid = (low + high + 1) / 2

high = mid - 1

low = mid

low是满足条件可能的值,mid是中间值,high右端值

     供暖器

    算法描述

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

现在,给出位于一条水平线上的房屋和供暖器的位置,找到可以覆盖所有房屋的最小加热半径。

所以,你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。

说明:

  • 给出的房屋和供暖器的数目是非负数且不会超过 25000。
  • 给出的房屋和供暖器的位置均是非负数且不会超过10^9。
  • 只要房屋位于供暖器的半径内(包括在边缘上),它就可以得到供暖。
  • 所有供暖器都遵循你的半径标准,加热的半径也一样。

示例 1:

输入: [1,2,3],[2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1,那么所有房屋就都能得到供暖。

示例 2:

输入: [1,2,3,4],[1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1,这样所有房屋就都能得到供暖。

    算法代码

    // 想法:先确定半径范围,再不断缩小范围
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
    	Arrays.sort(heaters);
        // t为满足供暖的房屋数量(前t个房屋)
        int mid, t, l = 0, h = Math.max(houses[houses.length - 1] - heaters[0], heaters[heaters.length - 1] - houses[0]);
        
        loop: 
        while(h > l){
            mid = (h + l - 1) / 2;
            t = 0;
            for(int ht: heaters){
                // 满足供暖的前t个房间小于所有房间(不是所有房间都满足供暖)
                while(t < houses.length){
                    // 第t+1个房间满足供暖
                    if(ht + mid >= houses[t] && ht - mid <= houses[t]){
                        t++;
                    }else{
                        break;
                    }
                }
                
                // 所有房间都满足供暖,说明当前的mid(半径)满足,使h=mid
                if(t == houses.length){
                    h = mid;
                    continue loop;
                }

            }
            
            // 当前mid(半径)不满足条件,增大mid(半径)
            l = mid + 1;
        }

        return h;
    }

    算法说明

    所求值在h, l之间,我们要求的是半径的最小值(最优解),怎么求呢,令满足要求的半径为h(开始为最大,即要求最小,先设为最大,然后慢慢减小),然后慢慢减小h,直到不满足条件,从而得到满足条件的最小h,high, low, mid三者判断、赋值的情况是

判断

while(h > l)

赋值

mid = (h + l - 1) / 2

h = mid

l = mid + 1

h是满足要求的可能值,mid是中间值,l是左端值


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

点赞(0) 打赏

全部评论

2021-04-16 09:21
广告位-帮帮忙点下广告