网站开发技术方法与路线,查公司信息的网站,下载ps软件免费版,wordpress国际运费设置给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。
示例 1: 输入: nums [1,3,5,6], target 5 输出: 2
示例 2: 输入:…给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 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 10 4 10^4 104 − 10 4 -10^4 −104 nums[i] 10 4 10^4 104 nums 为 无重复元素 的 升序 排列数组 − 10 4 -10^4 −104 target 10 4 10^4 104 知识点 数组、二分查找 解 核心思路二分查找
三个测试用例的分析
时间复杂度 O ( l o g n ) O(log n) O(logn)。 空间复杂度 O ( 1 ) O(1) O(1)。
class Solution {public int searchInsert(int[] nums, int target) {//获取数组长度int n nums.length;//定义二分查找的指针int low 0;int high n - 1;//只要两个指针不重合就继续循环while (low high) {//获取中位数int mid (low high) / 2;//判断是否存在if (nums[mid] target) {return mid;} else if (nums[mid] target) {high mid - 1;} else {low mid 1;}}//返回最终要添加元素的位置下标lowreturn low;}
}这里一开始我看成了要插入元素那么实现有一种很简单的方法采用辅助数组但空间复杂度较大 O ( n ) O(n) O(n)插入部分的代码应在while循环后、return语句前本题不要求插入因此这里仅作参考。 //定义辅助数组存储新数组int[] tmp new int[n 1];//到达这里时lowhigh表明数组不存在该元素则插入nums[low]if (low 0) {//插入的位置在数组开头tmp[0] target;//填充剩余元素for (int i 0; i n; i) {tmp[i 1] nums[i];}} else if (low n) {//插入的位置在数组末尾tmp[n] target;//填充剩余元素for (int i 0; i n; i) {tmp[i] nums[i];}} else {//插入的位置在数组中间//填充剩余元素for (int i n - 1; i low; i--) {tmp[i 1] nums[i];}tmp[low] target;for (int i 0; i low; i) {tmp[i] nums[i];}}参考 无
