LeetCode——Search Insert Position
程序员文章站
2024-03-15 21:17:24
...
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
解法一
public int searchInsert(int[] nums, int target) {
if(nums==null||nums.length==0||target<nums[0])
return 0;
int length=nums.length;
for(int i=0;i<length;i++)
{
if(target<=nums[i])
return i;
}
return length;
}
Runtime: 2 ms, faster than 100.00% of Java online submissions for Search Insert Position.
Memory Usage: 39.5 MB, less than 14.13% of Java online submissions for Search Insert Position.
解法二——利用二分搜索法
数组较大的话用二分法可能更快一点
public int searchInsert1(int[] nums, int target) {
if(nums==null||nums.length==0||target<nums[0])
return 0;
int length=nums.length;
if(nums[length-1]<target)
return length;
int start=0,end=nums.length-1;
while(start<end)
{
int mid=(start+end)/2;
if(nums[mid]==target)
return mid;
else if(nums[mid]<target)
start=mid+1;
else
end=mid;
}
return end;
}
Runtime: 2 ms, faster than 100.00% of Java online submissions for Search Insert Position.
Memory Usage: 39.4 MB, less than 22.91% of Java online submissions for Search Insert Position.
下一篇: 在一亿个数据中找出最大的100个
推荐阅读
-
LeetCode——Search Insert Position
-
【leetcode】35. Search Insert Position 给定数字插入有序数组的下标点
-
[leetcode]Search Insert Position
-
LeetCode: Search Insert Position
-
Search Insert Position -- LeetCode
-
【LeetCode】Search Insert Position
-
[Leetcode] -- Search Insert Position
-
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array
-
【LeetCode 5296】All Elements in Two Binary Search Trees【Medium】【JAVA】
-
[leetcode] Insert Interval