欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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区中看到两个解法

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/14699/Clean-iterative-solution-with-two-binary-searches-(with-explanation)

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/14701/A-very-simple-Java-solution-with-only-one-binary-search-algorithm

相同的是当nums[mid]>=target时不是令high=mid-1,而是high=mid;

第一个在找最后出现的位置的时候,将每一个mid都加1,相当于是做了偏移

第二个是找比target大的元素的位置来确定target最后出现的位置

能够顺着思路走下去,但是为啥要这样不是很懂


另一种想法是按照传统的二叉查找找到target的位置,之后再继续向前向后寻找,直到找到和target不同的元素的位置,但是这样会有问题,如果所有的元素都是一样的话,那么不就要把所有的元素都遍历一遍的嘛

但在别的博客上显示这种方法提交是通过的,神奇。