0%

LeetCode 035 Search Insert Position

发表于 更新于 分类于

Description

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2
Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2
Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2
Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2
Input: [1,3,5,6], 0
Output: 0

Difficulty: Easy

Code:

1
2
3
4
5
class Solution {
    public int searchInsert(int[] nums, int target) {
        
    }
}

题意

给定一个有序数组nums和一个目标值target，若数组中nums能找到target则返回下标，否则返回它应该放入的位置。数组中没有重复元素。

Solution 1

先把target大于或者小于nums所有数的情况解决掉，剩下就是在nums中进行二分查找。

若能找到则返回下标，若不能，则退出循环时left的位置即为应插入的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int searchInsert(int[] nums, int target) {
        if(nums==null||nums.length==0) return 0;
        int len=nums.length;
        if(target<nums[0]) return 0;
        if(target>nums[len-1]) return len;
        int left=0,right=len-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
}

时间复杂度: O()。

空间复杂度: O()。