LeetCode 35. Search Insert Position

题目

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.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

分析

  • 输入:一个有序数组,一个目标值
  • 任务:找到数组中小于目标值的元素个数
  • 条件:数组中没有重复数字
  • 输出:数组中小于目标值的元素个数

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
for i in range(len(nums)):
if nums[i] >= target:
return i
return len(nums)

解释

因为数组已经有序了,所以直接遍历数组就好,遍历到第一个大于等于目标值的元素时,输出下标就好,如果没有找到,那么直接输出数组长度