0034-leetcode算法实现之查找元素位置-find-first-and-last-position-of-element-in-sorted-array-python&golang实现

互联网 2021/10/14 1:14:57

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 进阶: 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗? 示例 1: 输入:nums = [5,7,7,8,8,10…

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1:

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

示例 2:

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

示例 3:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

python

class Solution:
    def searchRange(self, nums: [int], target: int) -> [int]:

        def search(nums: [int], target: int) -> int:
            left, right = 0, len(nums)
            while left < right:
                mid = int((left+right)/2)
                if nums[mid] >= target:
                    right = mid
                else:
                    left = mid + 1
            return left

        # 找到第一个=target的位置
        leftIdx = search(nums, target)
        # 找到第一个 > target的位置
        rightIdx = search(nums, target+1)
        if leftIdx == len(nums) or nums[leftIdx] != target:
            return [-1, -1]
        return [leftIdx, rightIdx-1]

if __name__ == "__main__":
    nums1 = [1,3]
    target1 = 2
    nums2 = [1,3,3,3,3,3,3,3,5,5,6]
    target2 = 5
    test = Solution()
    print(test.searchRange(nums1,target1)) # [-1, -1]
    print(test.searchRange(nums2,target2)) # [8, 9]

golang

func main() {
	var nums = []int{1, 3, 3, 3, 3, 3, 3, 3, 5, 5, 6}
	var target int = 5
	res := searchRange(nums, target)
	fmt.Println(res)
}

func searchRange(nums []int, target int) []int {
	//第一个=target的位置
	leftIdx := search(nums, target)
	rightIdx := search(nums, target+1)

	if leftIdx == len(nums) || nums[leftIdx] != target {
		return []int{-1, -1}
	}
	return []int{leftIdx, rightIdx - 1}
}

func search(nums []int, target int) int {
	var left int = 0
	var right int = len(nums)
	for left < right {
		var mid int = (left + right) / 2
		if nums[mid] >= target {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[0034-leetcode算法实现之查找元素位置-find-first-and-last-position-of-element-in-sorted-array-python&golang实现]http://www.zyiz.net/tech/detail-241131.html

上一篇:Python 格式化字符串传值问题(format() 与 %s)

下一篇:windows系统下搭建Python开发环境

赞(0)
关注微信小程序
程序员编程王-随时随地学编程

扫描二维码或查找【程序员编程王】

可以随时随地学编程啦!

技术文章导航 更多>
扫一扫关注最新编程教程