leetcode之-题34

题目

Search for a Range 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].

题解

想必大家看到时间要求O(log n),已经想到了需要使用二分查找,二分查找很简单,关键是这个题目要我们找到target的区间 其实很简单,分成两步就好了,第一次尽量向左走,第二次尽量向右走,获得左边和右边的位置,返回即可

  • (1)寻找最左的index: 找到相等时,high=mid,让它一直向左走
  • (2)寻找最右的index: 找到相等时,low=mid,让它一直向右走

代码

#!/usr/bin/python
# -*- coding:utf-8 -*-

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) == 0:
            return [-1, -1]
        start_index = self.lsearch(nums, target)
        end_index = self.rsearch(nums, target)
        return [start_index, end_index]

    def rsearch(self, nums, target):
        # 二分查找,相等时候一直向右
        low = 0
        high = len(nums) - 1
        while low < high - 1:
            mid_index = (low + high) // 2
            if nums[mid_index] > target:
                high = mid_index - 1
            elif nums[mid_index] < target:
                low = mid_index + 1
            else:
                low = mid_index
        if nums[high] == target:
            return high
        elif nums[low] == target:
            return low
        else:
            return -1

    def lsearch(self, nums, target):
        # 二分查找,一直向左走
        low = 0
        high = len(nums) - 1
        while low < high - 1:
            mid_index = (low + high) // 2
            if nums[mid_index] > target:
                high = mid_index - 1
            elif nums[mid_index] < target:
                low = mid_index + 1
            else:
                high = mid_index
        if nums[low] == target:
            return low
        elif nums[high] == target:
            return high
        else:
            return -1


if __name__ == '__main__':

    a = Solution()
    st = a.searchRange([1,8,8,8,8,9,9,10,10,10,11], 8)
    print st      

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

C语言程序设计教程(第三版)课后习题6.3

题目描述 求Sn=a+aa+aaa+…+aa…aaa(有n个a)之值,其中a是一个数字,为2。 例如,n=5时=2+22+222+2222+22222,n由键盘...

26212
来自专栏恰同学骚年

剑指Offer面试题:24.复杂链表的复制

  下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。

732
来自专栏阿杜的世界

Java并发-CopyOnWriteArrayList前言CopyOnWriteArrayList API例子1:插入(删除)数据的同时进行遍历例子2:不支持一边遍历一边删除结论参考资料

今天我们一起学习下java.util.concurrent并发包里的CopyOnWriteArrayList工具类。当有多个线程可能同时遍历、修改某个公共数组时...

983
来自专栏Spark学习技巧

JAVA集合框架中的常用集合及其特点、适用场景、实现原理简介

1043
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-向量实现《数据结构与算法分析》

#include <iostream> #include <list> #include <string> #include <vector> #include...

1886
来自专栏数据结构与算法

BZOJ1509: [NOI2003]逃学的小孩(树的直径)

第一行是两个整数N(3  N  200000)和M,分别表示居住点总数和街道总数。以下M行,每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti(1...

1192
来自专栏落花落雨不落叶

leetcode 34. Search for a Range

2746
来自专栏codingforever

经典算法巡礼(七) -- 排序之堆排序

很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现...

492
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

1023
来自专栏Java编程

Java HashMap那点事

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,其中 HashMap 是 Map 接口的常用实现类,...

3970

扫码关注云+社区