今天做这道!!
这也太简单了吧!!!实际上....他确实含简单...
35. 搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/implement-strstr
u1s1 看到这类题目我第一想法是用数组(谁看到这道题都知道用数组好吧!!!!)...
思路:
在说明思路之前,暂且将nums数组定义为A数组,target数字定义为B数字!
然后重头戏他来了!那就是——————
看到题目直接一个for循环遍历整个数组用if条件判断解决问题!
(......这也太简单了8....)
过程:
在这里需要考虑....在这里什么都不需要考虑完全就是宇宙级水题!(其实并不)如果你你和我一样想着“O(n)的复杂度你总不能给我超时吧!”,那么你可能和这个程序一样...
class Solution { public int searchInsert(int[] nums, int target) { for(int i=0;i<nums.length;i++) { if(nums[i]==target){ return i; }else if(nums[i]>target){ return i; }else{ continue; } } return nums.length; } }
但是实际上,这种题型一般要求采用二分法来完成。(虽然二分法和直接暴力搜实测感觉不出来区别....)我也使用二分法做了一遍,这里需要注意的是边界加减1的判断和输出,以下是二分法代码。
public int searchInsert(int[] nums, int target) { int left=0; int right=nums.length-1; while(left<=right){ int mid=(left+right)/2; if(nums[mid]>target){ right=mid-1; }else if(nums[mid]==target){ return mid; }else{ left=mid+1; } } return right+1; }