剑指Offer的学习笔记（C#篇）-- 数字在排序数组中出现的次数

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

题目描述

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

一 . 题目分析

该题目并不是难题，但该题目考察目的是正确的选择合适的查找方法。题目中有一个关键词是：排序数组，也就是说，该数组已经排好了，我一开始直接遍历了一遍数组，有相同的就加1，代码量虽然很少，但这很显然是效率很低的方法。所以又重新码了二分查找法的代码。

根据题意，使用这种方法要考虑到两点：

1. 把二分查找法先构造出来。

2. 统计数字k在数组中出现次数。

二 . 代码实现

class Solution
{
    public int GetNumberOfK(int[] data, int k)
    {
        // write code here
        // 鲁棒判断
        if (data.Length == 0)
        return 0;
// 使用二分查找法：定义前指针min，后指针max，中间指针mid，计数器count
        int min = 0,max = data.Length - 1,mid = 0,count = 0;
// 构建二分查找模型
        while(min <= max)
        {
            if (min > max)
            break;
            mid = (max+min)/2;
            if(data[mid] == k)
            {
                break;
            }
            else if(data[mid]<k)
            {
                min = mid+1;
            }
            else
            {
                max = mid-1;
            }
        }
// 若存在中间数 == k，给count赋值为1
        if(data[mid] == k)
        {
            count = 1;
        }
// 统计一个k在排序数组中出现的次数
        for (int i = 1; i < data.Length; i++)
            {
// 定义循环停止条件，提高效率
                bool firstFlag = false;
                bool secondFlag = false;

// 左侧重复数的累加
                if (mid - i >= 0 && data[mid - i] == k)
                {
                    firstFlag = true;
                    count++;
                }

// 右侧重复数的累加
                if (mid + i < data.Length && data[mid + i] == k)
                {
                    secondFlag = true;
                    count++;
                }

// 循环停止条件
                if (firstFlag == false && secondFlag == false)
                {
                    break;
                }
            }
// 返回次数
        return count;
    }
}