zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof.md

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

Tags - 题目标签

Description - 题目描述

EN:

English description is not available for the problem. Please switch to Chinese.

ZH-CN:

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

 

示例 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

 

注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
typescript	84 ms	41 MB	2021/12/22 18:23

function search(nums: number[], target: number): number {
  if (nums.length === 0) {
    return 0;
  }
  const firstIdx = divideFirst(nums, 0, nums.length-1, target);
  const lastIdx = divideLast(nums, 0, nums.length-1, target);

  return (firstIdx === -1 || lastIdx === -1) ? 0 : lastIdx - firstIdx + 1;
};


function divideFirst(nums: number[], start: number, end: number, target: number): number {
  if (start > end) {
    // 说明二分找完了都没找到，返回-1
    return -1;
  }
  const middleIdx = start + Math.floor((end - start) / 2);
  if (nums[middleIdx] === target) {
    if (nums[middleIdx - 1] === target) {
      return divideFirst(nums, start, middleIdx-1, target);
    } else {
      return middleIdx;
    }
  } else if (nums[middleIdx] > target) {
    return divideFirst(nums, start, middleIdx-1, target);
  } else {
    return divideFirst(nums, middleIdx+1, end, target);
  }
}

function divideLast(nums: number[], start: number, end: number, target: number): number {
  if (start > end) {
    // 说明二分找完了都没找到，返回-1
    return -1;
  }
  const middleIdx = start + Math.floor((end - start) / 2);
  if (nums[middleIdx] === target) {
    if (nums[middleIdx + 1] === target) {
      return divideLast(nums, middleIdx+1, end, target);
    } else {
      return middleIdx;
    }
  } else if (nums[middleIdx] > target) {
    return divideLast(nums, start, middleIdx-1, target);
  } else {
    return divideLast(nums, middleIdx+1, end, target);
  }
}

My Notes - 我的笔记

典型的二分法（分治法）解决最快的题目。

看到排序数组，想到二分法。

注意：排序数组的二分法不是快排的 partition，二分法 divide 是查找排序数组中的数字，partition 是将非排序数组原地交换位置，构造成枢轴左边的数都小于（大于）枢轴，右边的数都大于（小于）枢轴的形式。