hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

Leetcode算法【34在排序数组中查找元素】

2019-11-18杂谈搜奇网65°c
A+ A-

在之前ARTS打卡中,我每次都把算法、英文文档、技能都写在一个文章里,如许对我的协助是挺大的,然则可能给读者来讲,一会儿有这么多的输入,照样须要长时候的消化。

那我如今转变下体式格局,将每个模块细分化,而且形貌的更仔细点,如许就能够和人人更好地交换,更好地讨论详细的细节,也能让人人更好地消化所学的学问。

所以,后续的ARTS打卡,会尝试先将算法以及英文文档拆离开,11月,收成的时节,让我们继承前行,在秋日收成更多,进修更多。小编与你偕行!

Algorithm LeetCode算法

在排序数组中查找元素的第一个和末了一个位置
(https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

问题形貌:给定一个根据升序分列的整数数组 nums,和一个目的值 target。找出给定目的值在数组中的最先位置和完毕位置。

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

假如数组中不存在目的值,返回 [-1, -1]。

示例1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解法一:线性扫描法

由于这是一个简朴的一维数组,我们要在数组上举行查找,最笨的要领天然就是用通例的要领举行一个个遍历查找,在这里我们叫他线性扫描

起首,我们对输入的数组nums先从头至尾举行遍历,当碰到第一个目的数字target时中断遍历,并记录下地点的位置。假如没有碰到数字,申明全部数组都不存在该目的,则直接返回一个找不到数字的结果即可,在这里就是 [-1,-1]

在找到第一个数字的前提下,我们从数组的尾部往前遍历,碰到第一个目的数字时,就是我们须要的第二个目的数字(由于最左侧有一个已存在了,所以必定存在一个最右侧的数字不会发生找不到的状况)。

末了,我们输出结果即可。

/**
* 
* @Title      :  
* @Description: 线性扫描
* @param nums
* @param target
* @return
* @return     :int[]
* @throws
*/
public static int[] searchRange1(int[] nums, int target) {
    int[] range = {-1,-1};
    
    // 从头至尾遍历,先查找左侧的元素
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            range[0] = i;
            break;
        }
    }
        
    // 假如左侧的元素找到末了也没找到,那末申明数组里不存在此元素,直接返回找不到的结果[-1,-1]
    if (range[0] == -1) {
        return range;
    }
        
    // 从尾到头遍历,继承查找右侧的元素
    for (int j = nums.length - 1; j >= 0 ; j--) {
        if (nums[j] == target) {
            range[1] = j;
            break;
        }
    }
        
    return range;
}

解法二:二分查找

为何会想到用二分查找呢?由于给出的问题里形貌了,我们传入的数组是已排过序的,二分法能有用进步查找效力

一样的也是须要举行相似线性查找的体式格局,只不过此次我们查找的次数不会许多。起首,为了找到最左侧(或许最右侧)包括 target 的下标(而不是找到的话就返回 true ),所以在我们找到一个 target 后不能立时住手。我们须要继承搜刮,直到 lo == hi 且它们在某个 target 值处下标雷同。

另一个转变是 left 参数的引入,它是一个 boolean 范例的变量,指导我们在碰到 target == nums[mid] 时应当做什么。假如 lefttrue ,那末我们递归查询左区间,不然递归右区间。斟酌假如我们在下标为 i 处碰到了 target ,最左侧的 target 肯定不会出如今下标大于 i 的位置,所以我们永久不须要斟酌右子区间。当求最右下标时,原理一样实用。

该体式格局参考力扣官方题解https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-yi-/,感兴趣的同砚能够链接过去进修下。

public static int[] searchRange(int[] nums, int target) {
    int[] targetRange = {-1,-1};
    int leftIndex = searchIndex(nums, target,true);
    if (leftIndex == nums.length || nums[leftIndex] != target) {
        return targetRange;
    }
        
    targetRange[0] = leftIndex;
    targetRange[1] = searchIndex(nums, target, false) - 1;
        
    return targetRange;
}
    
// 遍历左区间或许右区间
private static int searchIndex(int[] nums,int target,boolean left) {
    int lo = 0;
    int length = nums.length;
    while (lo < length) {
        int mid = (lo + length) / 2;
        if (nums[mid] > target || (left && target == nums[mid])) {
            length = mid;
        } else {
            lo = mid + 1;
        }
        
    }
        
    return lo;
}

在上一次久长养成的打卡习气可万万不能丢呀 另有一个体系引见了二分法的文章,在这个题解里又做了一次引见,对你的二分法会有深入的明白。

所以,小编照样贴出地点来,https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/ 让人人去进修下,在这里就不举行赘述了,怕形貌错了,达不到作者想要的结果,所以在此说声抱歉啦。

写了良久,这是一份合适一般群众/科班/非科班的『进修线路』

久长养成的打卡习气可万万不能丢呀

Java 中的 final、finally、finalize 有什么差别?

求求你别再“从入门到摒弃了”,贵在对峙

「奔跑吧攻城狮」谢谢人人的关注,如今背景复兴「设想形式」赠你小编经心遴选设想形式书本。小编想打造一个高质量交换群,复兴「加群」或右下角点击「撩我 -> 一同学」解锁。

本文由博客一文多发平台 OpenWrite 宣布!

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
Leetcode算法【34在排序数组中查找元素】

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282379.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>