纵有疾风起
人生不言弃

剑指Offer面试题:32.数字在排序数组中出现的次数


一、题目:数字在排序数组中出现的次数

题目:统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3,由于3在这个数组中出现了4次,因此输出4。

二、解题思路

2.1 直接运用二分查找

  既然输入的数组是排序的,那么我们很自然地就能想到用二分查找算法。在题目给出的例子中,我们可以先用二分查找算法找到一个3。由于3可能出现多次,因此我们找到的3的左右两边可能都有3,于是我们在找到的3的左右两边顺序扫描,分别找出第一个3和最后一个3。因为要查找的数字在长度为n的数组中有可能出现O(n)次,所以顺序扫描的时间复杂度是O(n)。因此这种算法的效率和直接从头到尾顺序扫描整个数组统计3出现的次数的方法是一样的。

2.2 改进运用二分查找

  接下来我们思考如何更好地利用二分查找算法。假设我们是统计数字k在排序数组中出现的次数。在前面的算法中时间主要消耗在如何确定重复出现的数字的第一个k和最后一个k的位置上,有没有可能用二分查找算法直接找到第一个k及最后一个k呢?

  我们先分析如何用二分查找算法在数组中找到第一个k。二分查找算法总是先拿数组中间的数字和k作比较。如果中间的数字比k大,那么k只有可能出现在数组的前半段,下一轮我们只在数组的前半段查找就可以了。如果中间的数字比k小,那么k只有可能出现在数组的后半段,下一轮我们只在数组的后半段查找就可以了。如果中间的数字和k相等呢?我们先判断这个数字是不是第一个k。如果位于中间数字的前面一个数字不是k,此时中间的数字刚好就是第一个k。如果中间数字的前面一个数字也是k,也就是说第一个k肯定在数组的前半段,下一轮我们仍然需要在数组的前半段查找

  (1)GetFirstK:找到数组中第一个k的下标。如果数组中不存在k,返回-1

    private static int GetFirstK(int[] data, int k, int start, int end)    {        if (start > end)        {            return -1;        }        int middIndex = (start + end) / 2;        int middData = data[middIndex];        if (middData == k)        {            if ((middIndex > 0 && data[middIndex - 1] != k) || middIndex == 0)            {                return middIndex;            }            else            {                end = middIndex - 1;            }        }        else if (middData > k)        {            end = middIndex - 1;        }        else        {            start = middIndex + 1;        }        return GetFirstK(data, k, start, end);    }

  (2)GetLastK:找到数组中最后一个k的下标。如果数组中不存在k,返回-1

    private static int GetLastK(int[] data, int k, int start, int end)    {        if (start > end)        {            return -1;        }        int middIndex = (start + end) / 2;        int middData = data[middIndex];        if (middData == k)        {            if ((middIndex < data.Length - 1 && data[middIndex + 1] != k) || middIndex == end)            {                return middIndex;            }            else            {                start = middIndex + 1;            }        }        else if (middData > k)        {            end = middIndex - 1;        }        else        {            start = middIndex + 1;        }        return GetLastK(data, k, start, end);    }

  (3)GetNumberOfK:找到数组中第一个和最后一个k的下标进行减法运算得到最终结果

    public static int GetNumberOfK(int[] data, int k)    {        int number = 0;        if (data != null && data.Length > 0)        {            int first = GetFirstK(data, k, 0, data.Length - 1);            int last = GetLastK(data, k, 0, data.Length - 1);            if (first > -1 && last > -1)            {                number = last - first + 1;            }        }        return number;    }

三、单元测试

3.1 测试用例

    // 查找的数字出现在数组的中间    [TestMethod]    public void GetNumberTest1()    {        int[] data = { 1, 2, 3, 3, 3, 3, 4, 5 };        int actual = NumberOfKHelper.GetNumberOfK(data, 3);        Assert.AreEqual(actual, 4);    }    // 查找的数组出现在数组的开头    [TestMethod]    public void GetNumberTest2()    {        int[] data = { 3, 3, 3, 3, 4, 5 };        int actual = NumberOfKHelper.GetNumberOfK(data, 3);        Assert.AreEqual(actual, 4);    }    // 查找的数组出现在数组的结尾    [TestMethod]    public void GetNumberTest3()    {        int[] data = { 1, 2, 3, 3, 3, 3 };        int actual = NumberOfKHelper.GetNumberOfK(data, 3);        Assert.AreEqual(actual, 4);    }    // 查找的数字不存在    [TestMethod]    public void GetNumberTest4()    {        int[] data = { 1, 3, 3, 3, 3, 4, 5 };        int actual = NumberOfKHelper.GetNumberOfK(data, 2);        Assert.AreEqual(actual, 0);    }    // 查找的数字比第一个数字还小,不存在    [TestMethod]    public void GetNumberTest5()    {        int[] data = { 1, 3, 3, 3, 3, 4, 5 };        int actual = NumberOfKHelper.GetNumberOfK(data, 0);        Assert.AreEqual(actual, 0);    }    // 查找的数字比最后一个数字还大,不存在    [TestMethod]    public void GetNumberTest6()    {        int[] data = { 1, 3, 3, 3, 3, 4, 5 };        int actual = NumberOfKHelper.GetNumberOfK(data, 6);        Assert.AreEqual(actual, 0);    }    // 数组中的数字从头到尾都是查找的数字    [TestMethod]    public void GetNumberTest7()    {        int[] data = { 3, 3, 3, 3 };        int actual = NumberOfKHelper.GetNumberOfK(data, 3);        Assert.AreEqual(actual, 4);    }    // 数组中的数字从头到尾只有一个重复的数字,不是查找的数字    [TestMethod]    public void GetNumberTest8()    {        int[] data = { 3, 3, 3, 3 };        int actual = NumberOfKHelper.GetNumberOfK(data, 4);        Assert.AreEqual(actual, 0);    }    // 数组中只有一个数字,是查找的数字    [TestMethod]    public void GetNumberTest9()    {        int[] data = { 3 };        int actual = NumberOfKHelper.GetNumberOfK(data, 3);        Assert.AreEqual(actual, 1);    }    // 数组中只有一个数字,不是查找的数字    [TestMethod]    public void GetNumberTest10()    {        int[] data = { 3 };        int actual = NumberOfKHelper.GetNumberOfK(data, 2);        Assert.AreEqual(actual, 0);    }    // 鲁棒性测试,数组空指针    [TestMethod]    public void GetNumberTest11()    {        int actual = NumberOfKHelper.GetNumberOfK(null, 0);        Assert.AreEqual(actual, 0);    }

3.2 测试结果

  (1)测试通过情况

剑指Offer面试题:32.数字在排序数组中出现的次数插图

  (2)代码覆盖率

剑指Offer面试题:32.数字在排序数组中出现的次数插图(1)

 

文章转载于:https://www.cnblogs.com/edisonchou/p/4822740.html

原著是一个有趣的人,若有侵权,请通知删除

未经允许不得转载:起风网 » 剑指Offer面试题:32.数字在排序数组中出现的次数

分享到: 生成海报
avatar

评论 抢沙发

评论前必须登录!

立即登录   注册

切换注册

登录

忘记密码 ?

切换登录

注册

我们将发送一封验证邮件至你的邮箱, 请正确填写以完成账号注册和激活