[每日一道小算法（四十八）][数组] 数字在排序数组中出现的次数（剑指offer题）

亦凉 2023-07-06 11:55 12阅读 0赞

前言：  
我这个系列会一直更新下去，题型不局限于剑指offer的题，还有笔试面试，leetcode上面的题都会涉及，我会一直刷下去，为了提升自己的编码能力。如果对你们有用可以点个关注。谢谢啦！！！  
纵然我很菜，但是别放弃，终有成为大神的那一天。

### 题目描述 ###

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

### 题目解析 ###

这道题很简单，直接暴力解法就可以。遍历一遍数组就可以。但是这样的话，时间复杂度很高。就想着有没有稍微好一点的算法，就想到了二叉搜索树，通过二叉搜索树找到k的位置，然后在进行查找。这样的时间复杂度会好一点。在一个就是使用二分查找法，如果进行分半来进行查找，统计。看代码吧，表达能力比较差，看代码就能看懂了。

### 代码样例 ###

#### 使用自带二叉搜索树 ####

package com.asong.leetcode.GetNumberOfK;
    
    import java.util.Arrays;
    
    /** * 数字在排序数组中出现的次数 * 先使用二叉搜树进行遍历，找到第一个出现所找的值返回索引，根据这个索引 */
    public class Solution { 
        public int GetNumberOfK(int [] array , int k) { 
            int index = Arrays.binarySearch(array, k);
            if(index<0)return 0;
            int cnt = 1;
            for(int i=index+1; i < array.length && array[i]==k;i++)
                cnt++;
            for(int i=index-1; i >= 0 && array[i]==k;i--)
                cnt++;
            return cnt;
        }
    }

#### 二分查找法实现 ####

package com.asong.leetcode.GetNumberOfK;
    
    /** * 数字在排序数组中出现的次数 * 统计一个数字在排序数组中出现的次数 */
    public class solution { 
        public int GetNumberOfK(int [] array , int k) { 
            if(array==null||array.length==0||k<0)
            { 
                return 0;
            }
            int result = 0;
            int mid = array.length / 2;
            if(array[mid]>k)
            { 
                for (int i = 0; i < mid; i++) { 
                    if(array[i] == k)
                    { 
                        result++;
                    }
                }
            }else if (array[mid] < k)
            { 
                for (int i = mid+1; i < array.length; i++) { 
                    if(array[i] == k)
                    { 
                        result++;
                    }
                }
            }else { 
                result =1;
                for (int i = mid+1; i < array.length && array[i] == k; i++) { 
                        result++;
                }
                for (int i = mid-1; i >=0 && array[i] == k ; i++) { 
                    result++;
                }
            }
            return result;
        }
    }