LeetCode 35. 搜索插入位置

这篇具有很好参考价值的文章主要介绍了LeetCode 35. 搜索插入位置。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

二分查找法

题目要求“必须使用时间复杂度为 O(log n) 的算法”,因此,必然会想到二分查找算法。此题在标准二分查找的基础上增加了插入功能,如何实现呢?

假定插入位置为pos,则必然有nums[pos-1] < target < nums[pos],成立
假定元素在pos处存在,则必有nums[pos-1] < target == nums[pos]
合并为:nums[pos-1] < target <= nums[pos]
综上所述,我们得出最终目标:「在一个有序数组中找第一个大于等于 target的下标」

复杂度分析
时间复杂度:O(logn),n为nums的长度,二分查找算法时间复杂度为O(logn)。
空间复杂度:O(1),仅用常量空间存储变量。文章来源地址https://www.toymoban.com/news/detail-794245.html

Swift

func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        
        let cnt = nums.count
        var leftIdx = 0, rightIdx = cnt-1
        
        //为啥是cnt,因为可以少处理边界情况,比如target比所有元素都大时,结果就是cnt
        var ans = cnt
        
        while leftIdx <= rightIdx {
            let mid = (leftIdx + rightIdx) >> 1
            
            if target <= nums[mid] {
                rightIdx = mid - 1
                ans = mid
            }else {
                leftIdx = mid + 1
            }
        }
        
        return ans + 1
    }

OC

//由于要考虑到插入,位置为pos,有nums[pos-1] < target <= nums[pos],
//因此,问题转换为[找出第一个大于等于target的元素所在的位置]
- (NSInteger)searchInsert:(NSArray *)nums
                   target:(NSInteger)target {
    NSInteger cnt = nums.count;
    NSInteger left = 0, right = cnt - 1;
    NSInteger ans = cnt;//赋值为cnt可减少边界情况处理,如target大于所有元素,那么就在最后一个位置插入
    
    while (left <= right) {
        NSInteger mid = (left + right) >> 1;
        
        if (target <= [nums[mid] integerValue]) {
            ans = mid;
            right = mid - 1;
        }else {
            left = mid + 1;
        }
    }
    
    return ans;
}

到了这里,关于LeetCode 35. 搜索插入位置的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包