【小Y学算法】⚡️每日LeetCode打卡⚡️——16.搜索插入位置
【小Y学算法】⚡️每日LeetCode打卡⚡️——16.搜索插入位置
呆呆敲代码的小Y
发布于 2021-08-25 14:38:21
发布于 2021-08-25 14:38:21
????前言
???? 算法题 ???? |
|---|
- ???? 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程????
- ???? 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
- ???? 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧????！
- ???? 今天是力扣算法题持续打卡第16天????！
???? 算法题 ???? |
|---|
????原题样例
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n)的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0示例 5:
输入: nums = [1], target = 0
输出: 0提示:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 为无重复元素的升序排列数组
- -104 <= target <= 104
????C#方法一：普通法
思路解析 这道题跟上一篇的实现 strStr()挺相似的，都是给定一个目标值，返回索引
但是这个是从数组中查找，上一个是字符串！
分析一下可能出现四种情况
- nums[i]==target
- nums[i]>target
- nums[0]>target
- nums[nums.Length-1]
前三种对应if(nums[i] >= target) return i;，最后一种对应：return nums.Length;
代码：
public class Solution {
public int SearchInsert(int[] nums, int target) {
for(int i = 0; i < nums.Length; i++)
{
if(nums[i] >= target) return i;
}
return nums.Length;
}
}执行结果
通过
执行用时：76 ms，在所有 C# 提交中击败了99.07%的用户
内存消耗：24.7 MB，在所有 C# 提交中击败了44.39%的用户复杂度分析
时间复杂度：O(long n)
空间复杂度：O(1)????C#方法二：二分法
代码：
public class Solution {
public int SearchInsert(int[] nums, int target)
{
int low = 0;
int high = nums.Length - 1;
int mid = 0;
while (low <= high)
{
mid = (low + high) / 2;
if (target == nums[mid]) return mid;
else if (target > nums[mid]) low = mid + 1;
else high = mid - 1;
}
//以上是常规的二分法
if (target > nums[mid]) return mid + 1;
else return mid;
}
}执行结果
通过
执行用时：76 ms，在所有 C# 提交中击败了99.07%的用户
内存消耗：24.5 MB，在所有 C# 提交中击败了84.00%的用户????Java 方法一：二分法
此方法跟C#第一种解题思路一致，都是二分法的思路
代码：
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int l=0,r=n-1;
while(l<=r){
int mid=l+(r-l)/2;
if(nums[mid]<target)
l=mid+1;
else r=mid-1;
}
return l;
}
};执行结果
通过
执行用时：0ms，在所有 Java 提交中击败了100%的用户
内存消耗：37.8 MB，在所有 Java 提交中击败了87.55%的用户复杂度分析
时间复杂度：O(long n)
空间复杂度：O((1)????总结
- 今天是力扣算法题打卡的第十六天！
- 文章采用
C#和Java两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-08-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录