欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[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

这里两个代码的运行时间和占用内存看起来好像差不多,应该是测试数据不够大吧,所以才没有体现出很大的差别。
性能肯定是二分会比较好的。