leetcode35-搜索插入位置

原题

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 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

解法

思想

二分查找

代码

Java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        int mid;
        while(left<right-1){
            mid = (left+right)/2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target) left = mid;
            else if(nums[mid] > target) right = mid;
        }
        if(nums[left]>=target) return left;
        return left+1;
    }
}

Go(2020/07/05)

func searchInsert(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    for left < right{
        mid := (left+right)/2
        if nums[mid] == target { return mid }
        if nums[mid] < target{
            left = mid+1
        }else{
            right = mid
        }
    }
    if nums[left] < target { return left+1 }
    return left
}

Python(2020/07/05)

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums)-1
        while left < right:
            mid = (left+right)/2
            if nums[mid] == target : return mid
            if nums[mid] < target:
                left = mid+1
            else:
                right = mid
        if nums[left] < target : return left+1
        return left

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode35-%e6%90%9c%e7%b4%a2%e6%8f%92%e5%85%a5%e4%bd%8d%e7%bd%ae/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月1日
下一篇 2020年3月2日

相关推荐

  • leetcode509-斐波那契数

    原题 斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,   F(1) …

    算法 2020年1月21日
    0120
  • leetcode153-寻找旋转排序数组中的最小值

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月3日
    080
  • leetcode739-每日温度

    原题 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 te…

    算法 2019年12月11日
    0130
  • leetcode9-回文数

    原题 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例1: 输入: 121 输出: true 示例2: 输入: -121 输出: fa…

    算法 2020年2月28日
    0120
  • leetcode224-基本计算器

    原题 实现一个基本的计算器来计算一个简单的字符串表达式的值。 字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格 。 示例1: 输入: "1 + 1…

    算法 2020年1月26日
    0160
  • leetcode945-使数组唯一的最小增量

    原题 给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1。 返回使 A 中的每个值都是唯一的最少操作次数。 示例 1: 输入: [1,2,2] 输出: 1…

    算法 2020年3月22日
    0630
  • leetcode443-压缩字符串

    原题 给定一组字符,使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。 在完成原地修改输入数组后,…

    算法 2020年5月28日
    070
  • 蓝桥杯试题-小数第n位

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。  如果我们把有限小数的末尾加上无限多个…

    算法 2020年2月29日
    080
  • leetcode63-不同路径II

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月22日
    0130
  • leetcode151-翻转字符串里的单词

    原题 给定一个字符串,逐个翻转字符串中的每个单词。 示例 1: 输入: “the sky is blue” 输出: “blue is sky the” 示例 2: 输入: “ he…

    算法 2019年11月22日
    090

发表回复

登录后才能评论