做简单网站怎么做,视觉差网站设计,网站开发团队名称,wordpress图片文件夹在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(…在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [5,7,7,8,8,10], target 8 输出[3,4]
解题思路
1、使用两次二分查找算法分别查找目标值在数组中的开始位置和结束位置。2、第一次二分查找找到目标值的开始位置即最左侧的目标值。3、第二次二分查找找到目标值的结束位置即最右侧的目标值。4、如果数组中不存在目标值则返回[-1, -1]。
Java实现
public class FindFirstAndLastPositionOfElementInSortedArray {public int[] searchRange(int[] nums, int target) {int left findLeft(nums, target);int right findRight(nums, target);return new int[]{left, right};}// 二分查找目标值的起始位置private int findLeft(int[] nums, int target) {int left 0, right nums.length - 1;int result -1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {result mid;//向左查找相邻位是否存在一样的数值right mid - 1;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return result;}// 二分查找目标值的结束位置private int findRight(int[] nums, int target) {int left 0, right nums.length - 1;int result -1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {result mid;//向右查找相邻位是否存在一样的数值left mid 1;} else if (nums[mid] target) {left mid 1;} else {right mid - 1;}}return result;}public static void main(String[] args) {FindFirstAndLastPositionOfElementInSortedArray solution new FindFirstAndLastPositionOfElementInSortedArray();int[] nums {5, 7, 7, 8, 8, 10};int target 7;int[] range solution.searchRange(nums, target);System.out.println(Range: [ range[0] , range[1] ]); // Output: [3, 4]}
}
时间空间复杂度 时间复杂度O(log n)其中n为数组nums的长度。因为使用了两次二分查找算法。 空间复杂度O(1)。
