【剑指 offer】 在排序数组中查找数字

题目

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

我的答案

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    let resCount = 0;
    for (let num of nums) {
        if (num > target) {
            return resCount;

        } else if (num < target) {
            continue;
        } else {
            resCount++;
        }

    }
    return resCount;
};
​

根据数组的特性，非递减的有序数组。我们在出现比现有数组大的情况时，就可以返回结果了。

优化

为了更加快速算出数组数量，我们可以从数组的两边开始找目标数字，找到之后，将两个 index 相减即可算出重复数量。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    let lastIndex = nums.length - 1;
    for (let i = 0; i < nums.length;) {
        if (nums[i] > target || nums[lastIndex] < target || lastIndex<i) {
            return 0;
        }
        if(nums[i]===target && nums[lastIndex]===target){
            return lastIndex-i+1;
        }
        nums[i] < target ? i++ : null;
        nums[lastIndex] > target ? lastIndex-- : null;

    }
    return 0;
};
​