美文网首页
LeetCode 第34题:在排序数组中查找元素的第一个和最后一

LeetCode 第34题:在排序数组中查找元素的第一个和最后一

作者: 放开那个BUG | 来源:发表于2020-07-01 11:00 被阅读0次

    1、前言

    题目描述

    2、思路

    思路就是对左右两边都进行二分查找,确定左右边界。即对数组进行两次二分查找,首先对数组进行二分查找,确定左边界。确定左边界的方法是,如果遇到 nums[mid] == target,此时不需要返回,而是把右边界往左缩,即 right = mid - 1。while 循环条件是 left <= right,即 right 会减到 left > right,跳出循环。有人会怀疑将边界往左锁 right = mid - 1 会使得 left 不能到 target 的左边界去。不会出现这种情况,right 最终会到左边界的上一位,然后 left 最终会与 right 相等。当 left 到达左边界时,left > right 会跳出循环,所以 left 会是左边界。

    还有一种简单的方法是,找到 target 后,定义两个指针不断向两边扩展,但是这种扩展的方法确实没有二分快。但是如果想不出来,而是用扩展的方法吧,解出题还是好的。

    3、代码

    class Solution {
        public int[] searchRange(int[] nums, int target) {
            if(nums == null || nums.length == 0){
                return new int[]{-1,-1};
            }
            int start = leftSearch(nums,target);
            if(start == -1){
                return new int[]{-1,-1};
            }
            int end = rightSearch(nums,target);
            return new int[]{start,end};
        }
    
        int leftSearch(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] == target) {
                    // 别返回,收缩左侧边界
                    right = mid - 1;
                }
            }
            // 最后要检查 left 越界的情况
            if (left >= nums.length || nums[left] != target)
                return -1;
            return left;
        }
    
    
        int rightSearch(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else if (nums[mid] == target) {
                    // 别返回,收缩右侧边界
                    left = mid + 1;
                }
            }
            // 最后要检查 right 越界的情况
            if (right < 0 || nums[right] != target)
                return -1;
            return right;
        }
    }
    
    public class Q34_SearchRange {
    
        public int[] searchRange(int[] nums, int target) {
            if(nums == null || nums.length == 0){
                return new int[]{-1, -1};
            }
    
            int mid = binarySearch(nums, target);
            if(mid == -1){
                return new int[]{-1, -1};
            }
    
            int left = mid, right = mid;
            while((left - 1 >= 0 && nums[left - 1] == nums[left]) || (right + 1 <= nums.length - 1 && nums[right] == nums[right + 1])){
                if(left - 1 >= 0 && nums[left - 1] == nums[left]){
                    left--;
                }
                if(right + 1 <= nums.length && nums[right] == nums[right + 1]){
                    right++;
                }
            }
    
            return new int[]{left, right};
        }
    
        private int binarySearch(int[] nums, int target) {
            int left = 0, right = nums.length - 1;
    
            while(left <= right){
                int mid = (right - left) / 2 + left;
    
                if(nums[mid] == target){
                    return mid;
                }else if(nums[mid] > target){
                    right = mid - 1;
                }else if(nums[mid] < target){
                    left = mid + 1;
                }
            }
    
            return -1;
        }
        
    
        public static void main(String[] args) {
            int[] nums = {1};
            int target = 1;
            int[] res = new Q34_SearchRange().searchRange(nums, target);
            System.out.println(res[0] + ":" + res[1]);
        }
    }
    

    相关文章

      网友评论

          本文标题:LeetCode 第34题:在排序数组中查找元素的第一个和最后一

          本文链接:https://www.haomeiwen.com/subject/uckvfktx.html