app网站建设,有没有专门做数据分析的网站,外贸企业 网站,企业管理软件排行搜索插入位置
description
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], tar…搜索插入位置
description
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5 输出: 2
示例 2:
输入: nums [1,3,5,6], target 2 输出: 1
示例 3:
输入: nums [1,3,5,6], target 7 输出: 4
提示:
1 nums.length 104 -104 nums[i] 104 nums 为 无重复元素 的 升序 排列数组 -104 target 104
idea
算法真是优雅的艺术~虽然我还很粗糙! 搜索指定数据位置找不到则返回需要插入的位置。 因为加了小小的变动找不到返回应该插入的位置。已知数组升序我们可以把问题转换为找到首个大于等于target的位置
solution
class Solution {public int searchInsert(int[] nums, int target) {int left 0, right nums.length - 1, ans nums.length;while(left right){int mid (left right) / 2;if(target nums[mid]) left mid 1;else{ans mid;right mid - 1;} }return ans;}
}在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [5,7,7,8,8,10], target 8 输出[3,4] 示例 2
输入nums [5,7,7,8,8,10], target 6 输出[-1,-1] 示例 3
输入nums [], target 0 输出[-1,-1]
提示
0 nums.length 105 -109 nums[i] 109 nums 是一个非递减数组 -109 target 109
idea
类似上一题升序数组中查找元素联想到用二分查找。 需要找元素首次出现和最后一次出现的位置可以把基本的二分查找转化为找最左右出现的位置。
solution
class Solution {public int[] searchRange(int[] nums, int target) {int[] ans {getPos(nums, target, 0), getPos(nums, target, 1)};return ans;}public int getPos(int[] nums, int target, int flag){int left 0, right nums.length - 1, ans -1;while(left right){int mid (left right) / 2;if(nums[mid] target){ans mid;if(flag 0) right mid - 1;else left mid 1;}else if(nums[mid] target) right mid - 1;else left mid 1;}return ans;}
}
