内容简介:Given an array of integers nums sorted in ascending order, 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].
Given an array of integers nums sorted in ascending order, 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].
Example 1: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Example 2: Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
难度:medium
题目:
给定一升序整数数组,找出给定整数的起止边界。算法时间复杂度要为O(log n)
思路:二叉搜索
Runtime: 4 ms, faster than 65.40% of Java online submissions for Find First and Last Position of Element in Sorted Array.
Memory Usage: 30.5 MB, less than 28.29% of Java online submissions for Find First and Last Position of Element in Sorted Array.
class Solution { public int[] searchRange(int[] nums, int target) { int[] result = new int[2]; result[0] = binarySearch(nums, false, target); result[1] = binarySearch(nums, true, target); return result; } // false -> left, true -> right private int binarySearch(int[] nums, boolean direction, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { if (direction && mid < nums.length - 1 && nums[mid + 1] == target) { left = mid + 1; } else if (!direction && mid > 0 && nums[mid - 1] == target) { right = mid - 1; } else { return mid; } } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
新内容创业:我这样打造爆款IP
南立新、曲琳 / 机械工业出版社 / 2016-5-10 / 39.00
这是个内容创业爆棚的时代,在采访几十家内容创业公司,与一线最优秀的创业者独家对话之后,作者写作了这本书,其中包括对这个行业的真诚感触,以及希望沉淀下来的体系化思考。 本书共分三个部分讲述了爆红大号的内容创业模式和方法。其中第一部分,讲述了新的生产方式,即内容形态发展的现状--正在被塑造;第二部分,讲述了新的盈利探索,即从贩卖产品到贩卖内容的转变,该部分以多个案例进行佐证,内容翔实;第三部分,......一起来看看 《新内容创业:我这样打造爆款IP》 这本书的介绍吧!