[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

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].
public int[] searchRange(int[] nums, int target) {
        int low = 0, high = nums.length - 1, temp = -1;
        int result[] = new int[2];
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                temp = mid;
                break;
            }
            if (nums[mid] > target)
                high = mid - 1;
            if (nums[mid] < target)
                low = mid + 1;
        }
        if (temp == -1) {
            Arrays.fill(result, -1);
            return result;
        }
        int tmp = temp;
        while (tmp > 0 && target == nums[tmp - 1])
            tmp--;
        while (temp < nums.length-1 && target == nums[temp + 1])
            temp++;
        result[0] = tmp;
        result[1] = temp;
        return result;
    }

上discuss看了简单一些的方法吧,分享下。

public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (nums[left] == target && nums[right] == target)
                    return new int[] { left, right };
                else if (nums[left] != target)
                    left++;
                else
                    right--;
            } else if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return new int[] { -1, -1 };
    }
目录
相关文章
Leetcode 74. Search a 2D Matrix
这道题很简单,为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序,且每一行第一个数都大于上一行末尾数的矩阵,让你判断某个数在这个矩阵中是否存在。 假设矩阵是m*n,扫一遍的时间复杂度就是O(m*n),题目中给出的这么特殊的矩阵,时间复杂度可以降到O(m+n),具体代码如下,写的比较挫。
86 1
LeetCode 307. Range Sum Query - Mutable
update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。
104 0
LeetCode 307. Range Sum Query - Mutable
LeetCode 304. Range Sum Query 2D - Immutable
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2)。
104 0
LeetCode 304. Range Sum Query 2D - Immutable
|
索引
LeetCode 303. Range Sum Query - Immutable
给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
93 0
LeetCode 303. Range Sum Query - Immutable
LeetCode 212. Word Search II
给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
79 0
LeetCode 212. Word Search II
LeetCode 201. Bitwise AND of Numbers Range
给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。
70 0
LeetCode 201. Bitwise AND of Numbers Range
|
索引
LeetCode 81. Search in Rotated Sorted Array II
假设按升序排序的数组在事先未知的某个枢轴处旋转。 (例如, [0,0,1,2,2,5,6] 可能变成 [2,5,6,0,0,1,2]). 给定一个要搜索的目标值T, 如果该目标值能在数组中找到则返回true,否则返回false。
90 0
LeetCode 81. Search in Rotated Sorted Array II
|
索引
LeetCode 79. Word Search
给定一个2D板和一个单词,找出该单词是否存在于网格中。 该单词可以由顺序相邻的单元的字母构成,其中“相邻”单元是水平或垂直相邻的单元。 相同的字母单元格不得多次使用。
74 0
LeetCode 79. Word Search
|
算法
LeetCode 74. Search a 2D Matrix
编写一个有效的算法,搜索m×n矩阵中的值。 此矩阵具有以下属性: 每行中的整数从左到右排序. 每行的第一个整数大于前一行的最后一个整数.
80 0
LeetCode 74. Search a 2D Matrix
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree