LeetCode怎么搜索插入位置

小编给大家分享一下LeetCode怎么搜索插入位置,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!

一,搜索插入位置

1.1,问题简述

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

你可以假设数组中无重复元素。

 

1.2,示例

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

 
 

1.3,题解思路

本题主要采用的思路是基于集合和二分查找进行解决的,使用集合set的目的是为了去重,使用二分查找的目的是为了降低时间复杂度的,这就是本题的大致思路了。

 

1.4,题解程序

import java.util.*;
import java.util.stream.Collectors;

/**
* @author pc
*/
public class SearchInsertTest {
   public static void main(String[] args) {
       int[] array = {1, 3, 5, 6};
       int target = 0;
       int searchInsert = searchInsert(array, target);
       System.out.println("searchInsert = " + searchInsert);
   }

   public static int searchInsert(int[] nums, int target) {
       Set<Integer> set = new LinkedHashSet<>(nums.length);
       for (int num : nums) {
           set.add(num);
       }
       set.add(target);
       List<Integer> list = new ArrayList<>(set);
       List<Integer> collect = list.stream().sorted(Integer::compareTo).collect(Collectors.toList());
       int[] result = new int[collect.size()];
       int i = 0;
       for (int num : collect) {
           result[i++] = num;
       }

       int left = 0;
       int right = list.size() - 1;
       while (left <= right) {
           int mid = (right + left) / 2;
           if (target == result[mid]) {
               return mid;
           } else if (target > result[mid]) {
               left = mid + 1;
           } else {
               right = mid - 1;
           }
       }
       return -1;
   }
}

看完了这篇文章,相信你对“LeetCode怎么搜索插入位置”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!

原创文章,作者:kirin,如若转载,请注明出处:https://blog.ytso.com/223644.html

(0)
上一篇 2022年1月7日
下一篇 2022年1月7日

相关推荐

发表回复

登录后才能评论