剑指 Offer 53 – I. 在排序数组中查找

本问题对应的 leetcode 原文链接:剑指 Offer 53 – I. 在排序数组中查找
对应打卡问题:【二叉树专题】剑指 Offer 53 – I. 在排序数组中查找

问题描述

统计一个数字在排序数组中出现的次数。

示例1 :

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

示例 2:

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

提示:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    public int search(int[] nums, int target) {
        //常见题型:
        // 1.寻找第一个大于等于 target 的数   2.寻找第一个等于 target 的数
        // 3.寻找最后一个大于等于 target 的数 4.寻找最后一个等于 target 的数
        //PS:其实这里是不需要写两个查找函数的,可以把代码优化放在同一个方法里滴
        int left = search2(nums, target);
        int right = search4(nums, target);

        if(left < 0 || right < 0) return 0;
        return right - left + 1;



    }
    //2.寻找第一个等于 target 的数的下标
    int search2(int[] nums, int target){
        if(nums == null || nums.length <= 0){
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while(left < right){
            // 向下取整
            int mid = (right - left) / 2 + left;
            if(nums[mid] >= target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        // 判断该数是否存在
        if(nums[left] != target) return -1;
        return left;
    }

    //4.寻找最后一个等于 target 的数下标
    int search4(int[] nums, int target){
        if(nums == null || nums.length <= 0){
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while(left < right){
            //向上取整
            int mid = (right - left + 1) / 2 + left;
            if(nums[mid] <= target){
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        // 判断该数是否存在
        if(nums[left] != target) return -1;
        return left;
    }

}

时间复杂度:log(n)
额外空间复杂度:O(1)

发表回复

后才能评论