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

34. 在排序数组中查找元素的第一个和最后一个位置【二分待完成】

程序员文章站 2022-06-07 23:42:41
...

题目来源

leetcode

题目描述

34. 在排序数组中查找元素的第一个和最后一个位置【二分待完成】

题目解析

前后双指针

第一反应前后双指针
但是题目中提出算法时间复杂度必须是 O(log n) 级别,就是指明了要用折半查找,然而既然想到了就写一下,巩固巩固,(*_ *)

    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if (nums == null){
            return res;
        }


        int low = 0;
        int high = nums.length -1;

        while (low < high){
            /*
             跳出循环的情况:
                没有目标: low = nums.length , high = nums.length - 1, 直接返回结果{-1, -1}
                有目标:   nums[low] == target, low = low
            * */
            while (low <= high && nums[low] != target){
                low++;
            }

            if (low == nums.length){
                return res;
            }

            res[0] = low;
            /*
            跳出循环的情况:while (low <= high && nums[high] != target)
                没有目标: 不可能,到了这一步,就至少有一个目标, 因此可以简写while (nums[high] != target)
                找到目标:
            * */
            while (nums[high] != target){
                high--;
            }
            res[1] = high;
        }

        return res;
    }

但是结果一定是超出时间限制
时间复杂度O(N),空间复杂度O(1)

线性扫描

    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if (nums == null){
            return res;
        }

        int left = -1;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == target){
                left = i;
                break;
            }
        }

        if (left == -1){
            return res;
        }

        res[0] = left;

        // 此时left一定不为-1
        int right = left; // right 至少有一个值:left
        for (int j = nums.length - 1; j > left; j--){
            if (nums[j] == target){
                right = j;
                break;
            }
        }

        res[1] = right;


        return res;
    }

时间复杂度O(N),空间复杂度O(1)

二分查找

如果遇到“有序”,“算法时间复杂度是 O(log n) 级别”之类的就要考虑二分法了

相关标签: # 易错题