数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python中查找排序数组中元素的首尾位置
假设我们有一个整数数组A。这个数组按升序排序，我们需要找到给定目标值的起始和结束位置。当目标值在数组中找不到时，返回[-1, -1]。例如，如果数组是[2,2,2,3,4,4,4,4,5,5,6]，目标值是4，则输出为[4,7]
为了解决这个问题，我们将遵循以下步骤：
- 初始值 res := [-1,-1]，设置 low := 0，high := 数组A的长度
- 当 low < high
- mid := low + (high – low)/2
- 如果 A[mid] 等于目标值，则
- high := mid，res[0] := mid 且 res[1] := mid
- 否则，如果 A[mid] < 目标值，则 low := mid + 1，否则 high := mid
- 如果 res[0] = -1，则返回 res
- low := res[0] + 1，high := nums的长度
- 当 low < high
- mid := low + (high – low)/2
- 如果 A[mid] 等于目标值，则
- low := mid + 1，res[1] := mid
- 否则，如果 A[mid] < 目标值，则 low := mid + 1，否则 high := mid
- 返回 res
示例(Python)
让我们来看下面的实现来更好地理解：
class Solution(object): def searchRange(self, nums, target): res = [-1,-1] low = 0 high = len(nums) while low<high: mid = int(low + (high-low)//2) if nums[mid] == target: high = mid res[0]=mid res[1]=mid elif nums[mid]<target: low = mid+1 else: high = mid if res[0] == -1: return res low = res[0]+1 high = len(nums) while low<high: mid = int(low + (high-low)//2) if nums[mid] == target: low = mid+1 res[1] = mid elif nums[mid] < target: low = mid + 1 else: high = mid return res ob1 = Solution() print(ob1.searchRange([2,2,2,3,3,4,4,4,4,5,5,6], 4))
输入
[2,2,2,3,4,4,4,4,5,5,6] 4
输出
[5, 8]
更新于: 2020年4月27日
870 次浏览
广告