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

秒速五厘米 2023-09-26 16:57 17阅读 0赞

package com.example.demomain.demoleetcode.easy;
    import java.util.Arrays;
    /**
     * 统计一个数字在排序数组中出现的次数。
     *
     * 示例 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
     */
    public class Search {
        
        /**
         * 查找出现次数
         * @param nums
         * @param target
         * @return
         */
        public int searchTimes(int[] nums, int target) {
        
           return Math.toIntExact(Arrays.stream(nums).boxed().filter(e -> e.equals(target)).count());
        }
        public int searchTimes1(int[] nums, int target) {
        
            // 目标值的最后一个索引减去 小于目标值的第一个值的索引
            return findTarget(nums, target) - findTarget(nums, target - 1);
        }
    
        /**
         * 双指针
         * @param nums
         * @param target
         * @return
         */
        public int findTarget(int[] nums, int target) {
        
            int left = 0, right = nums.length - 1;
            while(left <= right) {
        
                int mid = (left + right) / 2;
                if(nums[mid] <= target) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    }