LeetCode(35):搜索插入位置
2023-09-14 08:59:35 时间
Easy!
题目描述:
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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
解题思路:
该题目只需要遍历一遍原数组,若当前数字大于或等于目标值,则返回当前坐标,如果遍历结束了,说明目标值比数组中任何一个数都要大,则返回数组长度n即可。
C++解法一:
1 class Solution { 2 public: 3 int searchInsert(vector<int>& nums, int target) { 4 for (int i = 0; i < nums.size(); ++i) { 5 if (nums[i] >= target) return i; 6 } 7 return nums.size(); 8 } 9 };
当然,我们还可以用二分搜索法来优化我们的时间复杂度,而且个人认为这种方法应该是面试官们想要考察的算法吧。
C++解法二:
1 class Solution { 2 public: 3 int searchInsert(vector<int>& nums, int target) { 4 if (nums.back() < target) return nums.size(); 5 int left = 0, right = nums.size() - 1; 6 while (left < right) { 7 int mid = left + (right - left) / 2; 8 if (nums[mid] == target) return mid; 9 else if (nums[mid] < target) left = mid + 1; 10 else right = mid; 11 } 12 return right; 13 } 14 };
相关文章
- Java实现 LeetCode 826 安排工作以达到最大收益(暴力DP)
- Java实现 LeetCode 783 二叉搜索树节点最小距离(遍历)
- Java实现 LeetCode 779 第K个语法符号(递归)
- Java实现 LeetCode 643 子数组最大平均数 I(滑动窗口)
- Java实现 LeetCode 999 车的可用捕获量(简单搜索)
- Java实现 LeetCode 556 下一个更大元素 III(数组的翻转)
- Java实现 LeetCode 324 摆动排序 II
- Java实现 LeetCode 240 搜索二维矩阵 II(二)
- Java实现 LeetCode 112 路径总和
- Java实现 LeetCode 109 有序链表转换二叉搜索树
- Java实现 LeetCode 35 搜索插入位置
- Java实现 LeetCode 33 搜索旋转排序数组
- Java实现 LeetCode 240 搜索二维矩阵 II
- LeetCode(34):搜索范围
- [LeetCode] Linked List Cycle
- LeetCode(109):有序链表转换二叉搜索树
- LeetCode(96): 不同的二叉搜索树
- LeetCode-1792. 最大平均通过率【堆,优先队列,贪心】
- LeetCode-1139. 最大的以 1 为边界的正方形【前缀和,矩阵】
- LeetCode-669. 修剪二叉搜索树【DFS,二叉搜索树】
- ( “树” 之 BST) 669. 修剪二叉搜索树 ——【Leetcode每日一题】
- 【LeetCode 35】搜索插入位置
- 【LeetCode Python实现】33. 搜索旋转排序数组(中等)
- 【LeetCode 简单 数组】35 搜索插入位置
- [LeetCode] 95. 不同的二叉搜索树 II ☆☆☆(递归,n个数组成的所有二叉搜索树)
- leetcode 17 -- Letter Combinations of a Phone Number
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点