LeetCode-搜索插入位置(35)

2024-01-10 13:32:13

题目描述:

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。
在这里插入图片描述
思路: 给定数组查找指定元素值的索引,如果元素值不存在于数组,就返回被顺序插入位置,并且时间复杂度要求O(log n),那么很自然就能想到使用二分查找,当二分查找找不到元素值时后面再去考虑顺序插入的情况。如果原数组不包括给定的元素值那么就要寻找插入位置,在我看来插入位置分三种情况,第一种指定元素小于等于数组中第一个数,第二种指定元素值大于等于数组最后一个数,第三种就是大于等于前一个数,小于等于后一个数。具体看代码。

代码:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right) {
            int mid=(right+left)/2;
            if(nums[mid]<target) {
                left=mid+1;

            } else if(nums[mid]>target) {
                right=mid-1;
            } else {
                return mid;
            }
        }

        for(int i=0;i<nums.length-1;i++) {
            if(nums[i]<=target&&nums[i+1]>=target) {
                return i+1;
            } 
        }

        if(nums[nums.length-1]<=target) {
            return nums.length;
        }

        

        return 0;
    }
}

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