- 浏览: 176142 次
- 性别:
- 来自: 济南
文章分类
最新评论
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].
这道题目同样采用二分法,当找到目标元素后,因为存在重复元素,我们要从当前元素向两边扩散,然后得到一个范围。如何记录呢,我们可以new一个包含两个元素的数组result,当找到目标元素时,记录当前元素的下标m,让result[0] = m, result[1] = m, 然后以m为中心,向两边比较,左边相等的就让result[0]减1,右边相等的就让result[1]加1。最终得到了包含目标元素的范围。代码如下:
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].
这道题目同样采用二分法,当找到目标元素后,因为存在重复元素,我们要从当前元素向两边扩散,然后得到一个范围。如何记录呢,我们可以new一个包含两个元素的数组result,当找到目标元素时,记录当前元素的下标m,让result[0] = m, result[1] = m, 然后以m为中心,向两边比较,左边相等的就让result[0]减1,右边相等的就让result[1]加1。最终得到了包含目标元素的范围。代码如下:
public class Solution { public int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = -1; result[1] = -1; if(nums == null || target < nums[0] || target > nums[nums.length - 1]) return result; int l = 0; int r = nums.length - 1; while(l <= r) { int m = l + (r - l) / 2; if(nums[m] == target) { result[0] = m; result[1] = m; while(result[0] > 0 && nums[result[0] - 1] == target) result[0] --; while(result[1] < nums.length - 1 && nums[result[1] + 1] == target) result[1] ++; return result; } else if(nums[m] > target) { r = m - 1; } else { l = m + 1; } } return result; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 234Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 237You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 351Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 344Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 468Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 532Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 440Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 628Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 439The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 401Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 524Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 546Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 383All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 874Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 894Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 568Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 616Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 775Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 748You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 639For a undirected graph with tre ...
相关推荐
用于电动汽车充电寻找最优路径,以及充电站的分布
Search for a Range Search Insert Position Search in Rotated Sorted Array Search in Rotated Sorted Array II Search a 2D Matrix Search a 2D Matrix II Find Minimum in Rotated Sorted Array Find Minimum in...
In a single data structure, the GiST provides all the basic search tree logic required by a database system, thereby unifying disparate structures such as B+-trees and R-trees in a single piece of ...
1. Introduction 2. Array i. Remove Element ii. Remove Duplicates from Sorted Array iii....iv....v....vi....vii....viii....ix....x.... Search for a Range xiii. Search Insert Position xiv. Find Peak Element
Part I of the text describes major theoretical principles, and provides an extensive survey of specific techniques for a large range of applications. Part II concentrates on approaches particularly ...
Monte Carlo Tree Search (MCTS) is a recently proposed search method that combines the precision of tree search with the generality of random sampling. It has received considerable interest due to its ...
Here's what you need―a highly practical guide that gives you a quick start with ElasticSearch using easy-to-follow examples; get up and running with ElasticSearch APIs in no time Get the latest ...
There is a wide range of Cognitive Services APIs available. This book focuses on some of the most useful and powerful ways that your application can make intelligent use of language. Artificial ...
* Implementation of a Ternary Search Trie, a data structure for storing <code>String</code> objects * that combines the compact size of a binary search tree with the speed of a digital search trie, ...
and local search strategies This allows for a broad range of operations In particular a solver suite approach supports the flexible usage of the component solvers: one can execute fully automatic ...
The optimal search cost was also found to be for a function that did not include any buffer zone. The optimal, average search cost across the whole sample was 11% of the defined search area. Fifty-...
Creating a Macro to Search for Specific Numeric Values 102 Working with Dates Introduction 105 Checking Ranges for Dates (Using a DATA Step) 106 Checking Ranges for Dates (Using PROC PRINT) 107 ...
We study a range of syntactic processing tasks using a general...choice for a range of syntactic processing tasks and one that should be considered for comparison by developers of alternative approaches.
<span xss=removed>Similarity search is a common computational task in many applications. Distance-based indexing ... In a range search task, objects which satisfy the inclusion rule also satisfy t
Throughout the book, the key search components of metaheuristics are considered as a toolbox for: Designing efficient metaheuristics (e.g. local search, tabu search, simulated annealing, ...
Chapter 6 presents a technique for approximate answering range-sum queries on data cubes. To this end, the authors propose tree-based data structures for separately storing sampled data and outliers ...
However, if we are searching for multiple rows, such as duplicate values, or keys in a range, anything more than a small number of rows will make the nonclustered index search very inefficient. ...
After testing a range of alternatives, we have found that multiple randomized k-d trees provide the best performance for other datasets. We are releasing public domain code that implements these ...
the users of their applications the ability to search or filter through their data using a regular expression. Regular expressions are everywhere. Many books have been published to ride the wave of ...
applied in a wide range domain areas : network management, electronic commerce, energy efficiency and metering; Wireless Multimedia Sensors, grid computing and grid services, distributed data mining, ...