算法--微软面试：指定数字在数组中出现的次数

绝地灬酷狼 2022-06-14 11:46 89阅读 0赞

# **Q题目** #

在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。

--------------------

## **Answer解法** ##

这道题要求出结果不难，但要求最有解的话，就需要花费一番功夫了。常见解法有如下四种：

**定义：** 要查询的数字为key 查询的数组为arr

### 1）暴力穷举 ###

直接从头遍历计数就可以了

### 2）遍历开始和最后一次出现的index ###

*  从前开始遍历，遇到与key相同，则停止遍历，得到startIndex
 *  从后开始遍历，遇到与key相同，则停止遍历，得到endIndex
 *  数字出现次数为：endIndex-startIndex

该做法比方法一好一些，减少了一部分计算次数

--------------------

**方法一和方法二代码如下：**

package 微软面试题数字次数;
    
    import java.util.Arrays;
    import java.util.HashSet;
    
    public class Test1 {
        public static void main(String[] args) {
            int[] arr={
       1,3,7,7,7,7,8,9,9,10};
    
            System.out.println("方法一测试：不存在key--"+getNumTimes(arr, 11));
            System.out.println("方法一测试：存在一个key--"+getNumTimes(arr, 3));
            System.out.println("方法一测试：存多个key--"+getNumTimes(arr, 9));
    
            System.out.println();
            System.out.println("方法二测试：不存在key--"+getNumTimes2(arr, 11));
            System.out.println("方法二测试：存在一个key--"+getNumTimes2(arr, 3));
            System.out.println("方法二测试：存多个key--"+getNumTimes2(arr, 9));
    
        }
    
        //方法一：暴力解法--完整遍历
        public static int getNumTimes(int[] arr,int key){
            int count=0;
    
            //超出arr的最大值和最小值就没必要遍历了
            if(key>=arr[0]&&key<=arr[arr.length-1]){
                for (int i : arr) {
                    if(i==key){
                        count++;
                    }
                }
            }
    
            return count;
        }
    
        //方法二：遍历出开头和结尾
        public static int getNumTimes2(int[] arr,int key){
            int count=0;//key出现的次数
            int start=-1;//key第一次出现的位置--索引有index=0，所以这里用-1
            int end=-1;//key最后一次出现的位置
    
            //超出arr的最大值和最小值就没必要遍历了
            if(key>=arr[0]&&key<=arr[arr.length-1]){
                //计算start
                for (int i = 0; i < arr.length; i++) {
                    if(arr[i]==key){
                        start=i;
                        break;
                    }
                }
            }
    
            //计算end--若start为最后一个元素或key(即start=-1）不存在时，没必要求end了
            if(start!=-1 && start<arr.length-1){
                for(int i=arr.length-1;i>=0;i--){
                    if(arr[i]==key){
                        end=i;
                        break;
                    }
                }
                count=Math.abs(end-start+1);
            }
    
            return count;
        }
    
    }

**运行结果：**

![这里写图片描述][SouthEast]

--------------------

### 3）二分法查找所有数字 ###

直接使用二分法去查找所有出现的值，相对于前两种计算次数少一些

**代码如下：**

package 微软面试题数字次数;
    
    public class Test2 {
    
        //方法三：二分法查找
        //参数：arr--查找的数组  key--要查找的数字   
        //    startIndex和endIndex为在数组arr中的查找范围--startIndex:起始下标  endIndex:截止下标
        static int count=0;
        public static void getNumTimes4ByBinary(int[] arr, int key, int startIndex,int endIndex){
            int middle=(startIndex+endIndex)/2;
    
            if(startIndex>endIndex){
                return;//输入的参数不合法
            }
    
            if(arr[middle]==key){
                count++;
                //向前找
                 getNumTimes4ByBinary(arr, key, startIndex, middle-1);
                //向后找
                 getNumTimes4ByBinary(arr, key, middle+1, endIndex);
            }else if (arr[middle]<key) {
                 getNumTimes4ByBinary(arr, key, middle+1, endIndex);
            }else {
                 getNumTimes4ByBinary(arr, key, startIndex, middle-1);
            }
    
        }
    
        public static void main(String[] args) {
            int[] arr={
       1,3,7,7,7,7,8,9,9,10};
    
            getNumTimes4ByBinary(arr, 7, 0 , arr.length-1);
            System.out.println("方法三测试：存在多个key--"+count);
        }
    
    }

**注意：count为static变量，所以测试时，只能分别测试三种情况**

--------------------

### 4）二分法查找和for循环结合 ###

*  使用二分法查找数字，查询到第一个key后马上结束
 *  根据key的下标向前和向后遍历，直到与key不相同为止，获得count

**与前三种方法相比，大大减少了计算的次数，不过这还不是最佳算法**

**代码如下：**

**运行结果如下：**

![这里写图片描述][SouthEast 1]

--------------------

### 5）二分法查找开始和结束index ###

使用二分法查询开始和结束的index，关键是边界问题的判断。

**开始边界**：与前一个数字比较，若不相同则是边界

**结束边界**：与后一个数字比较，若不相同则是边界

**与方法四相比，大多数情况下，该方法更计算次数更少，在少部分情况下，方法是更好。但总体上方法5更好。**

**代码如下：**

package 微软面试题数字次数;
    
    public class Test3 {
        public static void main(String[] args) {
            int[] arr={
       1,3,7,7,7,7,8,9,9,10};
    
            System.out.println("方法五测试：不存在key--"+GetNumberOfK(arr, 11));
            System.out.println("方法五测试：存在一个key--"+GetNumberOfK(arr, 3));
            System.out.println("方法五测试：存多个key--"+GetNumberOfK(arr, 9));
    
        }
    
        // （1）GetFirstK：找到数组中第一个k的下标。如果数组中不存在k，返回-1
        public 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
        public 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;
        }
    
    }

**测试结果：**

![这里写图片描述][SouthEast 2]

[SouthEast]: /images/20220614/e15cd5fa193c4e1da342784b17b307a9.png
[SouthEast 1]: /images/20220614/e18d214e7a3b4d3c9608117bfd18add6.png
[SouthEast 2]: /images/20220614/53bad4817374461497bd8e517ae67798.png