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

发表评论
370 views

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

官方链接

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解法一

分别找左右边界，不烧脑

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] targetRange = {-1, -1};
        int n = nums.length;

        // 找左边界
        int low = 0;
        int high = n - 1;
        while(low <= high) {
            int mid = (low + high) >>> 1;
            if(nums[mid] > target) {
                high = mid - 1;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                if(mid == 0 || nums[mid-1] != target) {
                    targetRange[0] = mid;
                    break;
                } else {
                    high = mid - 1;
                }
            }
        }

        if (targetRange[0] == -1) {
            return targetRange;
        } else if (targetRange[0] == n - 1) {
            targetRange[1] = targetRange[0];
            return targetRange;
        }

        // 找右边界
        low = 0;
        high = n - 1;
        while(low <= high) {
            int mid = (low + high) >>> 1;
            if(nums[mid] > target) {
                high = mid - 1;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                if((mid == n-1) || (nums[mid+1] != target)) {
                    targetRange[1] = mid;
                    break;
                } else {
                    low = mid + 1;
                }
            }
        }

        return targetRange;
    }
}

解法二

class Solution {
    public int[] searchRange(int[] nums, int target) {

        int[] targetRange = {-1, -1};
        int leftIndex = extremeInsertIndex(nums, target, true);
        if(leftIndex == nums.length || nums[leftIndex] != target) {
            return targetRange;
        }

        targetRange[0] = leftIndex;
        targetRange[1] = extremeInsertIndex(nums, target, false) - 1;

        return targetRange;
    }

    public int extremeInsertIndex(int[]nums, int target, boolean isLeft) {
        int left = 0;
        int right = nums.length;

        while(left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (isLeft && target == nums[mid])) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

解法二

复杂度 非 log(n)

class Solution {
    public int[] searchRange(int[] nums, int target) {

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

        for(int i = nums.length - 1; i >=0; i--) {
            if (nums[i] == target) {
                result[1] = i;
                break;
            }
        }
        return result;
    }
}