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

34. 在排序数组中查找元素的第一个和最后一个位置

程序员文章站 2022-07-08 15:58:27
...

1.题目

34. 在排序数组中查找元素的第一个和最后一个位置

2.解法


class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        int result[] = {-1,-1};
        if(nums.length==0) return result;

        int count = 0;
        while(start <= end) {
            int mid = start + (end-start)/2;
            if(nums[mid] == target) {
                // 先判断左边
                int tmp = mid;
                // 直到最左边
                while (tmp > 0 && nums[--tmp] == target) {}
                if (tmp == 0 && nums[tmp] == target) {
                    result[count++] = tmp;
                } else {
                    result[count++] = tmp + 1;
                }
                
                // 再判断右边
                tmp = mid;
                while (tmp < nums.length - 1 && nums[++tmp] == target) {
                }
                if (tmp == nums.length - 1 && nums[tmp] == target) {
                    result[count] = tmp;
                } else {
                    result[count] = tmp -1;
                }
                break;
            }else if(nums[mid]< target){
                start = mid + 1;
            }else{
                end = mid-1;
            }
        }
       
        return result;
    }
}

时间复杂度为O(logn), 如果一个数字重复的次数很多的话,那么时间复杂度会变为O(n), 空间复杂度为O(1)

3.思考(可忽略)

这道题看看题解,很好~~

  1. 我忽略的最重要的一点是:
    @nums[i]==target时,左右两边都得判断,是否还有target
    我写的这个条件只满足,数组中只有两个重复数,并且mid-1、mid不在临界的情况

34. 在排序数组中查找元素的第一个和最后一个位置
如果改为这样,条件满足了,但是执行语句不满足了,所以,只有左右两边同时判断才对,不能只走一条道

34. 在排序数组中查找元素的第一个和最后一个位置
2、如果start = 0 , end = length的时候,条件为start < end, 因为前一个mid刚判断过。

3、临界条件一定要判断。

相关标签: Leetcode打卡