LeetCode--Java实现704.二分查找、278.第一个错误的版本、35.搜索插入位置

吾日三省贾斯汀 发表于 2021/10/13 23:04:22 2021/10/13
【摘要】 学习背景 本文主要介绍如何通过Java实现LeetCode官方提供的以下数据结构与算法题目: 704.二分查找278.第一个错误的版本35.搜索插入位置 目录 学习背景704...

在这里插入图片描述

学习背景

本文主要介绍如何通过Java实现LeetCode官方提供的以下数据结构与算法题目:

  • 704.二分查找
  • 278.第一个错误的版本
  • 35.搜索插入位置

704.二分查找

题目分析

原题:

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

解题思路

  • 数据结构与算法:数组 + 二分查找
  • 实现思路:设定左右指针,找出中间位置,并判断该位置值是否等于 target
    nums[mid] == target 则返回该位置下标
    nums[mid] > target 则右侧指针移到中间
    nums[mid] < target 则左侧指针移到中间
  • 时间复杂度:O(logN)对数复杂度

代码实现

具体代码:

/**
 * LeetCode:704.二分查找
 **/
public class LeetCode704 {
    public static void main(String[] args) {
        int[] nums = {-1,0,3,5,9,12};
        int target = 9;
//        int[] nums = {-1,0,3,5,9,12};
//        int target = 2;
        System.out.println(search(nums,target));;
    }

    /**
     * 数据结构与算法:数组 + 二分查找
     * 实现思路:设定左右指针,找出中间位置,并判断该位置值是否等于 target
     * nums[mid] == target 则返回该位置下标
     * nums[mid] > target 则右侧指针移到中间
     * nums[mid] < target 则左侧指针移到中间
     * 时间复杂度:O(logN) 对数复杂度
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums,int target){
        int left = 0,right = nums.length -1;
        while (left <= right){//循环
            int mid =left + (right - left)/2; //加上left指针,目的在于确保mid指针不会出现在left指针之前
            if (nums[mid] == target){
                return mid;
            }else if (nums[mid] > target){
                right = mid - 1; //mid - 1原因在于mid不是目标值,可直接剔除掉即取它的前一个给right指针
            }else{
                left = mid + 1; //mid + 1原因在于mid不是目标值,可直接剔除掉即取它的后一个给left指针
            }
        }
        return -1;
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

输出结果:

4

  
 
  • 1

278.第一个错误的版本

题目分析

原题:

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1:

输入:n = 5, bad = 4
输出:4
解释:
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。

示例2:

输入:n = 1, bad = 1
输出:1

提示:

1 <= bad <= n <= 231 - 1

解题思路

  • 数据结构与算法:二分查找
  • 实现思路:设定左右边界版本号,找出中间版本号,并判断该版本号是否是正确版本号
    isBadVersion(mid) == true,则将right右边界移到mid中间
    isBadVersion(mid) == false,则将left边界移到mid中间往后一个位置
  • 时间复杂度:O(logN)对数复杂度

代码实现

/**
 * LeetCode:278.第一个错误的版本
 **/
public class LeetCode278 {
    private static int count = 0;  //调用了API接口的次数统计
    public static void main(String[] args) {
//        int n = 5;
        int n = (1 << 31) - 1; //即 2的31 -1,位运算中有个口诀叫:左移n位表示乘以2的n次方,右移n位,则表示除以2的n次方
        System.out.println(firstBadVersion(n));
        System.out.println("调用API接口次数:" + count);
    }

    public static int firstBadVersion(int n) {
        int left = 1,right = n; //定义左、右边界
        while (left < right){//循环
            //int mid = left + (right - left) / 2; //取整的效率不比位运算效率高
            int mid = left + ((right - left) >> 1); //计算中间位置,加left目的是确保mid指针不会出现在left指针之前
            if(isBadVersion(mid)){//如果中间位置已经问题版本了,那表明第一个坏的版本肯定在中间位置之前即[left,mid]范围
                right  = mid; //将right右边界移到mid中间
            }else{//如果中间位置还是正常版本,那表明第一个坏的版本肯定在中间位置之后即[mid + 1,right]范围
                left = mid + 1; //将left边界移到mid中间往后一个位置
            }
        }
        return left; //通过while循环后,此时left和right边界已经是同一个版本了,此时该版本就是第一个问题版本
    }

    /**
     * 模拟问题版本号的API
     */
    public static boolean isBadVersion(int mid){
        count++;
        int randomNum = (int)(Math.random() * 100) + 1;//取1~100的随机整数,其中Math.random()是[0.0-1.0)之间的double数
        if (0 == (mid % randomNum)){//这里假设中间版本对随机整数求余为0,则返回true,表示该版本的junit单元测试有问题即该版本号是问题版本号
            return true;
        }else{//否则说明该该版本号是正常版本号
            return false;
        }
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

35.搜索插入位置

题目分析

原题:

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

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

示例 4:

输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:

输入: nums = [1], target = 0
输出: 0

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

解题思路

  • 数据结构与算法:二分查找
  • 实现思路:定义left左下标、right右下标以及目标元素要存储的元素下标ans,计算中间位置mid
    当nums[mid] >= target,设定ans = mid以及将right右下标向中间mid - 1位置移动
    否则nums[mid] < target,将left左下标向中间mid + 1位置移动
  • 时间复杂度:O(logN)对数复杂度

代码实现

/**
 * LeetCode:35. 搜索插入位置
 **/
public class LeetCode35 {
    public static void main(String[] args) {
        int[] nums = {1,3,5,6}; int target = 5;
//        int[] nums = {1,3,5,6}; int target = 2;
//        int[] nums = {1,3,5,6}; int target = 7;
//        int[] nums = {1,3,5,6}; int target = 0;
//        int[] nums = {1}; int target = 0;
        System.out.println(searchInsert(nums,target));
    }

    public static int searchInsert(int[] nums,int target){
        int n = nums.length;
        int left = 0; //左下标
        int right = n -1; //右下标
        int ans = n; //假设该位置是要插入元素的下标位置
        while (left <= right){//循环
            //int mid =left + (right - left) / 2; //取整的效率不比位运算高,位运算中有个口诀叫:左移n位表示乘以2的n次方,右移n位,则表示除以2的n次方
            int mid =left + ((right - left) >> 1); //中间元素下标,计算时加上left指针,目的在于确保mid指针不会出现在left指针之前
            if (nums[mid] >= target){//说明目标元素插入下标位置在[left,mid]范围
                ans = mid; //假设中间元素的下标刚好是要插入元素的下标位置
                right = mid - 1; //将右下标,向中间移动,mid - 1原因在于mid不是目标位置,可直接剔除掉即取它的前一个给right下标
            }else{
                left = mid + 1; //将左下标,向中间移动,mid + 1原因在于mid不是目标位置,可直接剔除掉即取它的后一个给left下标
            }
        }
        return ans; //循环执行完后,该值即为目标元素要插入的下标位置
    }

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

文章来源: blog.csdn.net,作者:吾日三省贾斯汀,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/JustinQin/article/details/120740114

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。