[Leetcode] -- Search Insert Position
程序员文章站
2024-03-15 21:03:45
...
分析:就是找到第一个大于或等于给出数字的位置。
代码一,直接按照这个逻辑实现:
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int i;
for(i=0;i<nums.size();i++)
{
if(nums[i]>=target)
return i;
}
return i;
}
};//Runtime: 8 ms, Memory Usage: 8.9 MB
但是当数据一大,这个代码的效率就很低,因为时间复杂度是O(N),另一个思路就是二分查找。
代码二,二分查找实现,时间复杂度O(log2N):
class Solution
{
public:
int searchInsert(vector<int>& v, int target)
{
int low=0,up=v.size()-1,mid;
if(v[up]<target) return up+1;
while(low<up)
{
mid=low+(up-low)/2;
if(v[mid]==target)
return mid;
else if(v[mid]<target)
low=mid+1;
else
up=mid;
}
return up;
}
};//Runtime: 8 ms, Memory Usage: 9 MB
这里两个代码的运行时间和占用内存看起来好像差不多,应该是测试数据不够大吧,所以才没有体现出很大的差别。
性能肯定是二分会比较好的。
推荐阅读
-
LeetCode: Search Insert Position
-
Search Insert Position -- LeetCode
-
[Leetcode] -- Search Insert Position
-
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array
-
【LeetCode 5296】All Elements in Two Binary Search Trees【Medium】【JAVA】
-
[leetcode] Insert Interval
-
LeetCode-34-Search for a Range
-
LeetCode-35-Search Insert Position
-
LeetCode-35-Search Insert Position
-
LeetCode-79-Word Search*