【剑指Offer】037——数字在排序数组中出现的次数 （数组）

题目描述

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

解题思路

正常的思路就是二分查找了，我们用递归的方法实现了查找k第一次出现的下标，用循环的方法实现了查找k最后一次出现的下标。
除此之外，还有另一种奇妙的思路，因为data中都是整数，所以我们不用搜索k的两个位置，而是直接搜索k-0.5和k+0.5这两个数应该插入的位置，然后相减即可。

参考代码

Java

public class Solution {
    public int GetNumberOfK(int[] array , int k) {
        int len = array.length;
        if (len == 0) return 0;
        int first = getFirst(array, k, 0, len -1); // 获取第一次出现k的索引
        int last = getLast(array, k, 0, len -1); // 获取最后一次出现k的索引
        // 确保查询到
        if (first != -1 && last != -1){
            return  last - first + 1;
        }
        return 0;
    }
    public int getFirst(int[] array, int k, int start, int end){
        int mid;
        // 查找 数据k的左边开始的那个索引
        while (start <= end){
            mid = start + (end - start) / 2;
            if (k <= array[mid]) end = mid - 1;
            else start = mid + 1;
        }
        // 确保在while循环中找到， start向右走
        if (start < array.length && array[start] == k) return start;
        else return -1;
    }
    public int getLast(int[] array, int k, int start, int end){
        int mid;
        while (start <= end){
            mid = start + (end - start) / 2;
            if (k>= array[mid]) start = mid + 1;
            else end = mid - 1;
        }
        // end 向左走
        if (end >= 0 && array[end] == k) return end;
        else return -1;
    }
    public int GetNumberOfK2(int[] array , int k){
        return biSearch(array, k + 0.5) - biSearch(array, k - 0.5);
    }
    // 查找
    public int biSearch(int[] array, double k){
        int start = 0, end = array.length - 1;
        while (start <= end){
            int mid = start + (end - start) / 2;
            if (array[mid] > k) end = mid - 1;
            else start = mid + 1;
        }
        return start;
    }
}

Python

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return self.biSearch(data, k + 0.5) - self.biSearch(data, k - 0.5)
    def biSearch(self, data, k):
        start, end = 0, len(data)  - 1
        while start <= end:
            mid = start + (end - start)/2
            if data[mid] > k: end = mid - 1
            else: start = mid + 1
        return start

个人订阅号

image