专栏首页Rude3Knife的后端开发专栏[Leetcode][python/java]Search for a Range/有序数组中的单一元素

[Leetcode][python/java]Search for a Range/有序数组中的单一元素

题目大意

查找升序数组第一次出现target数字的范围,返回索引号。题目要求的时间复杂度是O(log n)。

解题思路

二分查找变种,二分法时间复杂度就是O(log n)

代码

Java: 重复数组中的二分法找最左

https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3.md#%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE

public int[] searchRange(int[] nums, int target) {
    int first = binarySearch(nums, target);
    int last = binarySearch(nums, target + 1) - 1;
    if (first == nums.length || nums[first] != target)
        return new int[]{-1, -1};
    else
        return new int[]{first, Math.max(first, last)};
}

private int binarySearch(int[] nums, int target) {
    int l = 0, h = nums.length; // 注意 h 的初始值
    while (l < h) {
        int m = l + (h - l) / 2;
        if (nums[m] >= target)
            h = m;
        else
            l = m + 1;
    }
    return l;
}

Python:二分法找到后直接往前后遍历

class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return a list of length 2, [index1, index2]
    def searchRange(self, A, target):
        left = 0; right = len(A) - 1
        while left <= right:
            mid = (left + right) / 2
            if A[mid] > target:
                right = mid - 1
            elif A[mid] < target:
                left = mid + 1
            else:
                list = [0, 0]
                if A[left] == target: list[0] = left
                if A[right] == target: list[1] = right
                for i in range(mid, right+1):
                    if A[i] != target: list[1] = i - 1; break
                for i in range(mid, left-1, -1):
                    if A[i] != target: list[0] = i + 1; break
                return list
        return [-1, -1]

总结

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2018 Wannafly summer camp Day3--Shopping

    Shopping 描述 题目描述: 你要买n件物品,其中有一些是凳子。

    Enterprise_
  • 2018 Wannafly summer camp Day3--Knight

    Knight 题目描述: 有一张无限大的棋盘,你要将马从(0,0)(0,0)(0,0)移到(n,m)(n,m)(n,m)。 每一步中,如果马在(x,...

    Enterprise_
  • HDU 6354--Everything Has Changed(判断两圆关系+弧长计算)

    Enterprise_
  • C#脚本实践(四): 反射与序列化

    逍遥剑客
  • 2018 Wannafly summer camp Day8--区间权值

    区间权值 小Bo有nnn个正整数a1a1a_1……anana_n,以及一个权值序列w1w1w_1……wnwnw_n,现在她定义f(l,r)=(∑ri=la2...

    Enterprise_
  • atan和atan2反正切计算

    返回值 若不出现错误,则返回 arg 在[−π/2;+π/2][−π/2;+π/2] [- π/2 ; +π/2] 弧度范围中的弧(反)正切( arctan...

    Enterprise_
  • POJ 1113--Wall(计算凸包)

    Wall Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 40363 ...

    Enterprise_
  • POJ 1410--Intersection(判断线段和矩形相交)

    Intersection Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

    Enterprise_
  • 2018 Wannafly summer camp Day3--Travel

    Travel 描述 题目描述: 魔方国有n座城市,编号为1∼n1∼n1\sim n。城市之间通过n-1条无向道路连接,形成一个树形结构。

    Enterprise_
  • HDU 6330--Visual Cube(构造,计算)

    Enterprise_

扫码关注云+社区

领取腾讯云代金券