LeetCode——剑指 Offer 53 - I. 在排序数组中查找数字 I（Java）

题目描述

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

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

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

题解思路

返回一个数字在数组中出现的次数，注意这是要一个排序数组

其实最早想到的办法就是双指针，个人觉得这应该是最好的办法

因为存在数组为空的情况，会报一个空指针异常，其他就是常规操作，代码就不给除了

这里还有两种方法分别是二分查找和哈希表法，简单题，想必代码不难看懂

正确代码

    // 哈希表
    public int search1(int[] nums, int target) {
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            if (hashMap.containsKey(num)) {
                hashMap.put(num, hashMap.get(num) + 1);
            } else {
                hashMap.put(num, 1);
            }
        }
        if (hashMap.containsKey(target)) {
            return hashMap.get(target);
        }
        return 0;
    }

    // 二分查找
    public int search2(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        }
        return 0;
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

总结

其实这里双指针的方法是因为自己写的很不优雅，所以就没给出

并且官方的二分查找法说实话我是不太明白的，如果想看思路请参照官方文档

如果文章存在问题或者有更好的题解，欢迎在评论区斧正和评论，各自努力，你我最高处见

LeetCode——剑指 Offer 53 - I. 在排序数组中查找数字 I（Java）

原文：https://www.cnblogs.com/bc-song/p/15019779.html