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

Offer_53_1

题目描述

方法一：使用HashMap

package com.walegarrett.offer;

/**

 * @Author WaleGarrett

 * @Date 2021/2/9 20:10

 */

import java.util.HashMap;

import java.util.Map;

/**

 * 题目描述：统计一个数字在排序数组中出现的次数。

 */

/**

 * 方法一：使用HashMap存储数字出现的次数

 */

public class Offer_53 {

    public int search(int[] nums, int target) {

        Map<Integer,Integer> map = new HashMap<>();

        for(int num : nums){

            int val = map.getOrDefault(num, 0);

            val++;

            map.put(num, val);

        }

        return map.getOrDefault(target, 0);

    }

}

方法二：二分法分别找上下边界

/**

 * 方法二：使用二分法

 */

class Offer_53_2 {

    public int search(int[] nums, int target) {

        int len = nums.length;

        int i=0, j = len-1;

        while(i<=j){

            int mid = (i+j)>>1;

            if(nums[mid] <= target){

                i= mid+1;

            }else j= mid-1;

        }

        int right = i;

        i=0; j = len-1;

        while(i<=j){

            int mid = (i+j)>>1;

            if(nums[mid] < target){

                i= mid+1;

            }else j= mid-1;

        }

        int left = j;

        return right-left-1;

    }

}

复杂度分析

• 时间复杂度 O(log N) ： 二分法为对数级别复杂度。
• 空间复杂度 O(1) ： 几个变量使用常数大小的额外空间。