leetcode array binarysearch|34. Find First and Last Position of Element in Sorted Array
程序员文章站
2024-03-20 17:36:52
...
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]
题目要求算法复杂度在O(logn),刚开始迷迷糊糊没想明白怎么样才可以是log的算法,于是写了一个时间复杂度为O(n)的算法,还自以为n要比logn小,智障!!
class Solution {
public int[] searchRange(int[] nums, int target) {
int first=-1;
int last=-1;
int index=0;
int[] ans=new int[2];
for(;index<nums.length;index++){
if(nums[index]==target){
first=index;
break;
}
}
//index++;
for(;index<nums.length;index++){
if(nums[index]==target){
last=index;
}
}
if(first!=-1&&last!=-1){
ans[0]=first;
ans[1]=last;
return ans;
}
else{
ans[0]=-1;
ans[1]=-1;
return ans;
}
}
}
虽然最后通过了,但是还是不能这样写的!无序的话这样还行,题目既然给出有序,那就用折半二分这类的方法。
有n个节点的二叉树的高度为logn
自己写最后还是没有写出来,在discuss区中看到两个解法
相同的是当nums[mid]>=target时不是令high=mid-1,而是high=mid;
第一个在找最后出现的位置的时候,将每一个mid都加1,相当于是做了偏移
第二个是找比target大的元素的位置来确定target最后出现的位置
能够顺着思路走下去,但是为啥要这样不是很懂
另一种想法是按照传统的二叉查找找到target的位置,之后再继续向前向后寻找,直到找到和target不同的元素的位置,但是这样会有问题,如果所有的元素都是一样的话,那么不就要把所有的元素都遍历一遍的嘛
但在别的博客上显示这种方法提交是通过的,神奇。
推荐阅读
-
LeetCode:153. 寻找旋转排序数组中的最小值
-
leetcode array binarysearch|34. Find First and Last Position of Element in Sorted Array
-
leetcode 153. 寻找旋转排序数组中的最小值
-
LeetCode 153. 寻找旋转排序数组中的最小值 Python
-
LeetCode算法系列:34. Find First and Last Position of Element in Sorted Array
-
Find First and Last Position of Element in Sorted Array
-
LeetCode 153. 寻找旋转排序数组中的最小值
-
CSS Position 定位
-
css position 定位
-
Could not find rake-0.9.2 in any of the sources Run `bundle install` to install 博客分类: rails rubyrailsrubygems