Find First and Last Position of Element in Sorted Array
程序员文章站
2024-03-20 17:32:28
...
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
/**
* 从前往后找,从后往前找
* @param nums
* @param target
* @return
*/
public static int[] search1(int[] nums, int target)
{
int[] result = new int[]{-1,-1};
if(nums == null || nums.length == 0) return result;
for(int i = 0; i < nums.length; i++)
{
if(nums[i] == target)
{
result[0] = i;
break;
}
}
if(nums[0] == -1)
return result;
for(int i = nums.length-1; i>=0;i--)
{
if(nums[i] == target)
{
result[1] =i;
break;
}
}
return result;
}
/**
* 二分查找
* @param nums
* @param target
* @return
*/
public static int[] search2(int[] nums, int target)
{
int[] result = new int[]{-1,-1};
if(nums == null || nums.length == 0) return result;
int leftIndex = getIndex(nums,target,true);
if(leftIndex == nums.length || nums[leftIndex] != target)
return result;
int rightIndex = getIndex(nums,target,false) - 1;
result[0] = leftIndex;
result[1] = rightIndex;
return result;
}
public static int getIndex(int[] nums, int target, boolean flag)
{
int lo = 0;
int high = nums.length;
while(lo < high)
{
int mid = (lo + high) / 2;
if(nums[mid] > target || (flag && target == nums[mid]))
{
high = mid ;
}
else
{
lo = mid + 1;
}
}
return lo;
}
/**
* 二分查找
* @param nums
* @param target
* @return
*/
public static int[] search3(int[] nums, int target)
{
int[] result = new int[]{-1,-1};
if(nums == null || nums.length == 0) return result;
result[0] = FindFirst(nums,target);
result[1] = FindLast(nums,target);
return result;
}
/**
* 搜索左边第一个为target的元素
* @param nums
* @param target
* @return
*/
public static int FindFirst(int[] nums, int target)
{
int index = -1;
int lo = 0;
int hi = nums.length - 1;
while(lo <= hi)
{
int mid = (lo + hi) / 2;
if(nums[mid] >= target)
{
hi = mid - 1;
}
else
{
lo = mid + 1;
}
if(nums[mid] == target) index = mid;
}
return index;
}
/**
* 寻找最后一个target的索引
* @param nums
* @param target
* @return
*/
public static int FindLast(int[] nums,int target)
{
int index = -1;
int lo = 0;
int hi = nums.length - 1;
while(lo <= hi)
{
int mid = (lo + hi) / 2;
if(nums[mid] <= target)
{
lo = mid +1;
}
else
{
hi = mid - 1;
}
if(nums[mid] == target) index = mid;
}
return index;
}
上一篇: Java开发操作Cookie示例
推荐阅读
-
LeetCode算法系列:34. Find First and Last Position of Element in Sorted Array
-
Find First and Last Position of Element in Sorted Array
-
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array(C语言)
-
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array
-
BinarySearch[5]34. Find First and Last Position of Element in Sorted Array
-
Find First and Last Position of Element in Sorted Array
-
算法42--Find First and Last Position of Element in Sorted Array