小编给大家分享一下LeetCode怎么搜索插入位置,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
输入: [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
本题主要采用的思路是基于集合和二分查找进行解决的,使用集合set的目的是为了去重,使用二分查找的目的是为了降低时间复杂度的,这就是本题的大致思路了。
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怎么搜索插入位置”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
原文链接:https://my.oschina.net/u/3934278/blog/4795524