当前位置: 首页 > article >正文

优选算法的匠心之艺:二分查找专题(二)

专栏:算法的魔法世界

个人主页:手握风云

目录

一、例题讲解

1.1. 山脉数组的峰顶索引

1.2. 寻找峰值

1.3. 寻找旋转排序数组中的最小值

1.4. 点名


一、例题讲解

1.1. 山脉数组的峰顶索引

        题目很简单,要求我们在数组中找出一个值,这个值要比它左右元素都大。利用折线表示如下图所示。

        我们先想一个暴力解法:利用一个指针去遍历一遍数组,如果某个元素比它的下一个元素大,那么返回这个元素的下标。我们最坏情况下要遍历到倒数第二个元素,所以时间复杂度为O(n)

        从上图中我们已经可以看出,数组已经被分成两段,左边是递增的,右边是递减的,符合“二段性”,可以利用二分查找。如果arr[mid] > arr[mid-1],则left=mid(因为中间值可能就是我们要找的结果);如果arr[mid] < arr[mid-1],则right=mid-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;
    }
}

1.2. 寻找峰值

        与上一题不同的是,这道题的数组元素是上升、下降不断交替的。或者是递增的,或者是递减的。

        我们先来思考暴力解法:从第一个下标开始向后遍历,然后分情况讨论(如下图三种情况)。最坏情况下可能要走到最后一个元素,所以时间复杂度为O(n)

        如果走到了数组的某个位置i,此时的nums[i] > nums[i+1],那么在i的左边的区间一定会存在一个峰值;相反,如果nums[i] < nums[i+1],那么在i的右边的区间一定会存在一个峰值。这样就会把数组分成了两个部分,取其中一个区间去查找,那么我们就可以用二分查找进行优化。

        完整代码实现:

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])
                left = mid + 1;
            else 
                right = mid;
        }
        return left;
    }
}

1.3. 寻找旋转排序数组中的最小值

        题目有点长,我们首先需要理解旋转的定义。每旋转一次,将数组中最大的元素移动至最前面(如下图所示)。

        暴力解法:从头到尾遍历一边数组,比较出里面的最小值,时间复杂度为O(n)

        通过上面的示例1,我们可以很明显地发现“二段性”,左边是严格大于某个值的递增区间,右边是严格小于某个值递增区间,并且数组中没有重复元素,折线表示如下图所示。,我们以D点为参照物,“二段性”体现在AB区间是nums[i] > nums[i-1],CD区间是nums[i] < nums[i-1]。

        完整代码实现:

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.4. 点名

        题目解析:在一个升序数组中找到唯一一个缺失的数字并返回这个数字。

        这道题可以有多种解法。1.哈希表:创建一个长度为n-1的哈希表,将数组元素放入,空出的位置就是丢失的数字。2.直接遍历数组,找出某个位置断掉的元素。3.位运算。利用0——n-1与数组里的元素进行按位异或操作,相同的数字就可以消去,最后剩下的数字就是缺失的数字。但这几种算法的时间复杂度都为O(n)

        我们观察一下下图数组元素与下标的关系。在缺失的数字之前,数组元素与数组下标是一一对应的,到缺失的位置时,缺失的数字比数组元素小1。

        我们注意一个细节:如果给定的数组为[0,1,2,3],数组元素与下标都是一一对应的,而缺失的数字为最后一个元素加一。所以最后返回的时候,我们需要判断一下返回值的数组下标与数组元素是否相等。

        完整代码实现:

public 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;
        }
        return records[left] == left ? left + 1 : left;
    }
}

http://www.kler.cn/a/589416.html

相关文章:

  • C++洛谷基础练习题及解答
  • TCP简单链接的编程实现
  • 关于Redis的集群(上)
  • 高主频GPU+RTX4090:AI生图性能优化超150%
  • Netty基础—7.Netty实现消息推送服务一
  • llama.cpp 和 LLM(大语言模型)
  • 图 最 短 路
  • 【嵌入式学习】计算机组成原理-二进制存储基础
  • 【从零开始】Air780EPM的LuatOS二次开发——OneWire协议调试注意事项!
  • 【Linux】深入理解进程和文件及内存管理
  • Leetcode 不同路径 ||
  • 操作系统相关知识
  • 最短路径--dijkstra
  • Word 小黑第22套
  • 李宏毅NLP-1-课程介绍
  • 新能源汽车IGBT电压平台与SiC器件应用
  • 类和对象的创建
  • Python(1.1)Python实战:一键批量重命名图片文件,告别手动整理!(附完整源码)
  • python调用百度人脸识别接口
  • 【前端面试题】宏任务与微任务的区别