问题描述:
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1]
.
For example,
Given [5, 7, 7, 8, 8, 10]
and target value 8,
return [3, 4]
.
原问题链接:https://leetcode.com/problems/search-for-a-range/
问题分析
这个问题主要是要求在一个排序的数组里给定元素的最左边和最右边可能的位置。这也是相当于二分查找方法的一个变体。在二分查找的过程中,当我们找到nums[mid] == target的时候就返回mid表示找到这个位置的值了。但是针对要求它最左边和最右边可能的取值,我们就需要稍微做一点变动。
我们可以将这个问题先拆分成两个部分,比如说先求最左边位置的目标值。只要这个能够求出来,最右边的那个也就好办了。对于求最左边的目标值,我们可以定义一个临时的变量lpos。它的初始值为-1。当nums[mid] == target的时候,设置lpos = mid。同时将r = mid - 1。这样我们如果有更加左边的值的话通过这种方式可以找到后续的。而且这样可以逐步逼近到最终结果。
同理,求最右边的目标值也一样。只是需要稍微做一点修改。这样得到的最终代码实现如下:
public class Solution { public int[] searchRange(int[] nums, int target) { int l = 0, r = nums.length - 1, lpos = -1, rpos = -1; while(l <= r) { int mid = l + (r - l) / 2; if(nums[mid] == target) { lpos = mid; r = mid - 1; } else if(nums[mid] < target) l = mid + 1; else r = mid - 1; } if(lpos == -1) { int[] result = {-1, -1}; return result; } l = lpos; r = nums.length - 1; while(l <= r) { int mid = l + (r - l) / 2; if(nums[mid] == target) { rpos = mid; l = mid + 1; } else if(nums[mid] < target) l = mid + 1; else r = mid - 1; } int[] result = {lpos, rpos}; return result; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
LeetCode::laptop:LeetCode解决方案
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
LeetCode 101:和你一起你轻松刷题(C++)
for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个排序数组的中位数 (40_Hard) ...
Leetcode:Leetcode提交
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode:leetcode刷题
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
for Python :snake: Requirements Python >= 3.8 Installation git clone git@github.com:imajinyun/leetcode-python.git cd leetcode-python Usage python3 -m unittest discover -s ./tests/leetcode -t ./tests/...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
LeetCode:LeetCode的注释
leetcode:LeetCode问题
leetcode:LeetCode题解