This article is participating in Python Theme Month. See the link for details

Topic describes

This is the finger Offer 53-I on LeetCode. Finding the number I in a sorted array is easy.

Tag: “Dichotomy”

Count the number of occurrences of a number in a sorted array.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 output: 2Copy the code

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 output: 0Copy the code

Limitations:

  • 0 <= Array length <= 50000

Binary unilateral + linear scan

A naive idea is to find the subscript for the “first” or “last” occurrence of the target value targettargettarget, and then do a “back” or “forward” count.

Java code:

// Find the "last" segmentation point of the target value and count "forward"
class Solution {
    public int search(int[] nums, int t) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= t) l = mid;
            else r = mid - 1;
        }
        int ans = 0;
        while (r >= 0 && nums[r] == t && r-- >= 0) ans++;
        returnans; }}Copy the code
// Find the segmentation point where the target value appears "first" and count "later"
class Solution {
    public int search(int[] nums, int t) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= t) r = mid;
            else l = mid + 1;
        }
        int ans = 0;
        while (l < n && nums[l] == t && l++ >= 0) ans++;
        returnans; }}Copy the code

Python 3 code:

class Solution:
    # Find the "last" segmentation point of the target value and perform statistics "forward"
    def search(self, nums: List[int], t: int) - >int:
        n = len(nums)
        l, r = 0, n - 1
        while l < r:
            mid = l + r + 1 >> 1
            if nums[mid] <= t:
                l = mid
            else:
                r = mid - 1
        ans = 0
        while r >= 0 and nums[r] == t:
            ans += 1
            r -= 1
        return ans
Copy the code
class Solution:
   # Find the segmentation point where the target value appears "first" and count "later"
   def search(self, nums: List[int], t: int) - >int:
       n = len(nums)
       l, r = 0, n - 1
       while l < r:
           mid = l + r >> 1
           if nums[mid] >= t:
               r = mid
           else:
               l = mid + 1
       ans = 0
       while l < n and nums[l] == t:
           ans += 1
           l += 1
       return ans
Copy the code
  • Time complexity: after finding the segmentation point, scan forward or backward. The complexity is O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

On both sides of the binary

Further, we can directly find the left and right boundaries through two “dichotoms” and calculate the total length, which is the number of targettargettarget.

Java code:

class Solution {
    public int search(int[] nums, int t) {
        int n = nums.length;
        if (n == 0) return 0;
        int a = -1, b = -1;

        // Divide the left boundary
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= t) r = mid;
            else l = mid + 1;
        }
        if(nums[r] ! = t)return 0;
        a = r;

        // divide the right boundary
        l = 0; r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= t) l = mid;
            else r = mid - 1;
        }
        if(nums[r] ! = t)return 0;
        b = r;

        return b - a + 1; }}Copy the code

Python 3 code:

class Solution:
    def search(self, nums: List[int], t: int) - >int:
        n = len(nums)
        if not n:
            return 0
        a = b = -1

        # divide the left boundary
        l, r = 0, n - 1
        while l < r:
            mid = l + r >> 1
            if nums[mid] >= t:
                r = mid
            else:
                l = mid + 1
        
        ifnums[r] ! = t:return 0
        a = r

        # divide the right boundary
        l, r = 0, n - 1
        while l < r:
            mid = l + r + 1 >> 1
            if nums[mid] <= t:
                l = mid
            else:
                r = mid - 1
        
        ifnums[r] ! = t:return 0
        b = r
        return b - a + 1
Copy the code
  • Time complexity: O(log⁡n)O(\log{n})O(logn)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No. 53-I of our “Brush through LeetCode” series. The series started on January 21, 01/01, and there are 1916 questions on LeetCode by the start date.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.