数字在排序数组中出现的次数

1. 题目描述

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

2. 思路

• 暴力法
• 上界-下界：找到比k小一点的和比k大一点的数的插入位置即可，然后位置相减

3. 实现

3.1. 暴力法

//暴力法
//时间：O(N)
//空间：O(N)
func GetNumberOfK(data []int, k int) int {
	countMap := make(map[int]int, 0)
	for _, datum := range data {
		countMap[datum] ++
	}
	return countMap[k]
}

3.2. 上界-下界

• java

public class 数字在排序数组中出现的次数
{
    public static void main(String[] args)
    {
        System.out.println(new 数字在排序数组中出现的次数().GetNumberOfK(new int[]{4, 3, 3, 3, 2, 1}, 3));
    }

    public int GetNumberOfK(int[] array, int k)
    {
        //检查参数
        if (array == null || array.length == 0)
        {
            return 0;
        }
        //二分查找k-0.5需要插入的位置为idx1
        int idx1 = this.getBinarySearchInsertIndex(array, k - 0.5);
        //二分查找k+0.5需要插入的位置为idx2
        int idx2 = this.getBinarySearchInsertIndex(array, k + 0.5);

        //返回idx2-idx1
        return Math.abs(idx2 - idx1);

    }

    private int getBinarySearchInsertIndex(int[] array, double val)
    {
        int left = 0;
        int right = array.length - 1;
        //顺序的
        if (array[left] < array[right])
        {
            while (left <= right)
            {
                int mid = (left + right) >>> 1;
                if (val < array[mid])
                {
                    right = mid - 1;
                }
                else if (val > array[mid])
                {
                    left = mid + 1;
                }
            }
        }
        //逆序的
        else
        {
            while (left <= right)
            {
                int mid = (left + right) >>> 1;
                if (val < array[mid])
                {
                    left = mid + 1;

                }
                else if (val > array[mid])
                {
                    right = mid - 1;

                }
            }
        }
        return left;
    }

}

• go

//二分法
//时间复杂度：O(logN)
//空间复杂度：O(1)
func GetNumberOfK3(data []int, k int) int {
	right := UpperBinarySearch(data, k)
	left := LowerBinarySearch(data, k)
	return right - left - 1
}
func UpperBinarySearch(data []int, target int) int {
	left := 0
	// 有可能所有值都比target小，所以right初始化为数组长度表示这个值不存在
	right := len(data)
	for left < right {
		mid := (left + right) / 2
		midValue := data[mid]
		//中间值<=目标值，那么左边的所有值都是<=目标值，应该在右边找
		if midValue <= target {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return left
}

func LowerBinarySearch(data []int, target int) int {
	//可能数组中所有数都比target大，所以初始化left为-1表示不存在
	left := -1
	right := len(data) - 1
	for left < right {
		mid := left + (right-left+1)/2
		midValue := data[mid]
		//中间值<目标值，那么左边的所有值都是<目标值，应该在右边找
		if midValue < target {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}

4. 参考

• 数字在升序数组中出现的次数_牛客网
• 剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode）