ARTS leetcode9 Search Insert Position

太过爱你忘了你带给我的痛 2022-02-01 03:11 166阅读 0赞

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
    
    You may assume no duplicates in the array.
    
    Example 1:
    
    Input: [1,3,5,6], 5
    Output: 2
    Example 2:
    
    Input: [1,3,5,6], 2
    Output: 1
    Example 3:
    
    Input: [1,3,5,6], 7
    Output: 4
    Example 4:
    
    Input: [1,3,5,6], 0
    Output: 0

这道题目的意思是，给了一个排好序的数组和一个目标值，将目标值插入到数组中，如果找到了该目标则返回该索引，否则返回这个元素应该在哪里插入。

思路：  
（1）这个数组有值不为空  
（2）分情况，值在数组中存在和不存在；不存在的时候，且大于数组最大值，则返回的索引为数组的长度；如果小于数组的最小值，则返回0  
（3）存在于数组中的时候，如果该值大于等于目标值，那么就将该索引直接返回，跳出循环break。

class Solution {
        public int searchInsert(int[] nums, int target) {
             int index = 0;
            if(nums != null && nums.length > 0){
                int len = nums.length;
                if(Arrays.binarySearch(nums,target) <= 0 && target > nums[len-1]){
                    index = len;
                }
                for(int i=0;i<len;i++){
                    if((nums[i] == target)||(nums[i]>target)){
                        index = i;
                        break;
                    }
                }
            }
            return  index;
        }
    }

Runtime: 0 ms, faster than 100.00% of Java online submissions for Search Insert Position.
    Memory Usage: 39.6 MB, less than 6.42% of Java online submissions for Search Insert Position.

别人的解答，采用二分法，时间复杂度O(nLogN),代码如下：

思路：分别处理数组为空，target大于数组最大值和小于数组最小值的情况，然后使用二分法查找该元素在有序数组中的位置。

if(nums.length == 0) return 0;
        if(target <= nums[0]) return 0;
        if(target > nums[nums.length-1]) return nums.length;
        
        int low = 0;
        int high = nums.length-1;
        int mid = (low+high)/2;
        
        while(low != mid) {
            if(target == nums[mid]) return mid;
            if(target < nums[mid]) high = mid;
            else low = mid;
            mid = (low+high)/2;
        }
        return high;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20220201/557b83888daf49e4a595a6473cea1aae.png