C++实现LeetCode(35.搜索插入位置)

[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.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

这道题基本没有什么难度，实在不理解为啥还是 Medium 难度的，完完全全的应该是 Easy 啊（貌似现在已经改为 Easy 类了），三行代码搞定的题，只需要遍历一遍原数组，若当前数字大于或等于目标值，则返回当前坐标，如果遍历结束了，说明目标值比数组中任何一个数都要大，则返回数组长度n即可，代码如下：

解法一：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] >= target) return i;
        }
        return nums.size();
    }
};

解法二：

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

到此这篇关于C++实现LeetCode(35.搜索插入位置)的文章就介绍到这了,更多相关C++实现搜索插入位置内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(24.成对交换节点)

    [LeetCode] 24. Swap Nodes in Pairs 成对交换节点 Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed. Example: Given 1->2->3->4 , you should return t

  • C++实现LeetCode(31.下一个排列)

    [LeetCode] 31. Next Permutation 下一个排列 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sor

  • C++实现LeetCode(32.最长有效括号)

    [LeetCode] 32. Longest Valid Parentheses 最长有效括号 Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: "(()" Output: 2 Explanation: The longest valid

  • C++实现LeetCode(83.移除有序链表中的重复项)

    [LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项 Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1-

  • C++实现LeetCode(27.移除元素)

    [LeetCode] 27. Remove Element 移除元素 Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with

  • C++实现LeetCode(23.合并k个有序链表)

    [LeetCode] 23. Merge k Sorted Lists 合并k个有序链表 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 这

  • C++实现LeetCode(25.每k个一组翻转链表)

    [LeetCode] 25. Reverse Nodes in k-Group 每k个一组翻转链表 Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of n

  • C++实现LeetCode(35.搜索插入位置)

    [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. Example

  • C++实现LeetCode(74.搜索一个二维矩阵)

    C++实现LeetCode(74.搜索一个二维矩阵)

    [LeetCode] 74. Search a 2D Matrix 搜索一个二维矩阵 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is great

  • C++实现LeetCode(33.在旋转有序数组中搜索)

    [LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If f

  • C++实现LeetCode(81.在旋转有序数组中搜索之二)

    [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.

  • C++实现LeetCode(79.词语搜索)

    [LeetCode] 79. Word Search 词语搜索 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. Th

  • C++实现LeetCode(642.设计搜索自动补全系统)

    [LeetCode] 642. Design Search Autocomplete System 设计搜索自动补全系统 Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character '#'). For each character they type except '#', you ne

  • 基于B-树和B+树的使用：数据搜索和数据库索引的详细介绍

    基于B-树和B+树的使用：数据搜索和数据库索引的详细介绍

    B-树 1 .B-树定义 B-树是一种平衡的多路查找树,它在文件系统中很有用. 定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树:⑴树中每个结点至多有m 棵子树:⑵若根结点不是叶子结点,则至少有两棵子树: ⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树:⑷所有的非终端结点中包含以下信息数据: (n,A0,K1,A1,K2,-,Kn,An)其中:Ki(i=1,2,-,n)为关键码,且Ki<Ki+1, Ai 为指向子树根结点的指针(i=0,1,-,n),且指针Ai-1 所指子

  • python 输入字符串生成所有有效的IP地址(LeetCode 93号题)

    这题的官方难度是Medium,点赞1296,反对505,通过率35.4%.从各项指标来说看起来有些中规中矩,实际上也的确如此.这道题的解法和立意都有些显得新意不足,但总体来说题目的质量还是可以的,值得一做. 题意 给定一个由数字组成的字符串,我们希望通过这个字符串得到所有有效ip地址的组合.对于一个有效的ip地址而言,它应该有4个数字组成,每一个数字的范围在0到255之间. 一个字符串可能可以转化成多个ip地址,我们需要存储下来所有可以成立的情况. 样例 Input: "25525511135&

  • C++实现LeetCode(93.复原IP地址)

    [LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 这

  • C++实现LeetCode(119.杨辉三角之二)

    C++实现LeetCode(119.杨辉三角之二)

    [LeetCode] 119. Pascal's Triangle II 杨辉三角之二 Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle. Note that the row index starts from 0. In Pascal's triangle, each number is the sum of the two numbers directly

随机推荐