首页 > 代码库 > 【LeetCode】- Search Insert Position(查找插入的位置)
【LeetCode】- Search Insert Position(查找插入的位置)
[ 问题: ]
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.翻译:给你一个排好序的数组和一个目标值,请找出目标值可以插入数组的位置。[ 分析: ]
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
注意:一定要考虑一些特殊情况,如数组为null等。
[ 解法: ]
①. 常规解法:从数组索引为0的位置开始找,时间复杂度为O(n),accepted
public class Solution { public int searchInsert(int[] A, int target) { if (A != null) { for (int i = 0; i < A.length; i++) { if (target == A[i] || target < A[i]) { return i; } } return A.length; } return -1; } public static void main(String[] args) { int[] arr = { 1, 3, 5, 6 }; System.out.println(new Solution().searchInsert(arr, 5)); // 5 -> 2 System.out.println(new Solution().searchInsert(arr, 2)); // 2 -> 1 System.out.println(new Solution().searchInsert(arr, 7)); // 7 -> 4 System.out.println(new Solution().searchInsert(arr, 0)); // 0 -> 0 } }②. 二分查找:时间复杂度log2n
前提条件:一定是有序数组。
public class Solution { public int searchInsert(int[] A, int target) { int mid; int low = 0; int high = A.length - 1; while (low < high) { mid = (low + high) / 2; if (A[mid] < target) { low = mid + 1; } else if (A[mid] > target) { high = mid - 1; } else { return mid; } } return target > A[low] ? low + 1 : low; } public static void main(String[] args) { int[] arr = { 1, 3, 5, 6 }; System.out.println(new Solution().searchInsert(arr, 5)); // 5 -> 2 System.out.println(new Solution().searchInsert(arr, 2)); // 2 -> 1 System.out.println(new Solution().searchInsert(arr, 7)); // 7 -> 4 System.out.println(new Solution().searchInsert(arr, 0)); // 0 -> 0 } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。