专栏首页程序员小跃Leetcode算法【34在排序数组中查找元素】

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

在之前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/ 让大家去学习下,在这里就不进行赘述了,怕描述错了,达不到作者想要的效果,所以在此说声抱歉啦。

本文分享自微信公众号 - 奔跑吧攻城狮(runningdimple),作者:Dimple

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Dimple在左耳听风ARTS打卡(第一期)

    参加了左耳听风的ARTS打卡,坚持一个月,对自己会有什么情况呢,我不知道,但我会照着这个目标坚持下去,坚持100天。一个习惯养成是21天,那如果坚持100天,效...

    程序员小跃
  • Dimple在左耳听风ARTS打卡(十一)

    今天是端午节,也是高考的日子。小编当年是过了端午节高考的,今年也是赶上了,凑到了一起。你们家里人有要高考的吗?小编祝福他们。同时也祝各位端午节快乐!

    程序员小跃
  • Dimple在左耳听风ARTS打卡(第九期)

    所谓ARTS: 每周至少做一个LeetCode的算法题;阅读并点评至少一篇英文技术文章;学习至少一个技术技巧;分享一篇有观点和思考的技术文章。(也就是Algor...

    程序员小跃
  • 剑指Offer LeetCode 面试题53 - I. 在排序数组中查找数字 I

    输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2:

    TrueDei
  • Leetcode-Solutions 1.two-sum (Python&Golang)

    恩,最后找队友一起刷题。喜欢可以联系我 ,来公众号“Python爬虫与算法进阶”找我哦

    小歪
  • LeetCode68|和为s的两个数字

    双指针的使用,最近一段时间的输出文章都是自己之前做过的内容,自己打算将做过的题都整理成一篇篇文章进行梳理一下,喜欢看java的文章可以查看历史记录,本人写过My...

    后端Coder
  • LeetCode67|二分查找

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

    后端Coder
  • 每日算法题——两数之和

    许久不见,终于开始在公司上班了,有一点不好的就是一整天都要戴着口罩,闷得慌,不知道大伙儿有没有这种感觉。

    用户2802329
  • 【leetcode刷题】20T1-两数之和

    https://leetcode-cn.com/problems/two-sum/

    木又AI帮
  • Leetcode#1.Two Sum(两数之和)

    题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums ...

    武培轩

扫码关注云+社区

领取腾讯云代金券