LeetCode 35. 搜索插入位置

发布时间:2024年01月11日

搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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),仅用常量空间存储变量。

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;
}
文章来源:https://blog.csdn.net/zzl819954692/article/details/135536107
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。