数据结构与算法--数字在排序数组中出现次数

墨蓝 2022-10-09 12:16 156阅读 0赞

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

*  题目：统计一个数字在一个排序数组中出现的次数。例如，输入数组\{1,2，3，3,3，3,3，4,5\} 和数字3，由于3 在数组中出现的次数是5，因此返回5

#### 简单方案一 ####

*  既然输入的数组是有序的，那么最简单的方式是一次遍历，统计出需要的数字出现的个数，时间复杂度是O(n)，实现方法如下：

**
     * 查询有序数组中数字k 出现的次数
     *
     * @author liaojiamin
     * @Date:Created in 16:08 2021/6/24
     */
    public class GetNumberOfK { 
    
        public static void main(String[] args) { 
            int[] array = new int[]{ 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 33, 44, 55, 56, 56, 56, 56, 56, 57};
            System.out.println(countK(array, 0));
        }
    
        /** * 方法一，遍历统计 O(n) */
        public static Integer countK(int[] array, int k) { 
            if (array == null || array.length <= 0) { 
                return -1;
            }
            int count = 0;
            for (int i = 0; i < array.length; i++) { 
                if (array[i] == k) { 
                    count++;
                }
            }
            return count;
        }
     }

#### 方法二二分查找 ####

*  有序数组，而且是查询，那么时间效率最高的就是二分查找了，分析流程如下：
    
     *  如上案例中二分查找找出其中一个3 的位置，标记为position
     *  此时可能前后都还存在3，那么从position向前遍历，查找之前的3，得到firstK
     *  从position向后遍历，查找之后的3，得到lastK
     *  那么k出现的次数n = lastK - firstK + 1
 *  如上分析有如下代码：

*  如上算法因为k出现的次数可能是n次，那么我们向前向后遍历的次数可能就是n， 那么时间复杂度还是O(n)，并没有达到优化的目的。此算法中实际主要消耗在如何确定重复数字的第一个k与最后一个k的位置上。

#### 方案三纯二分查找 ####

*  方案二中既然可以通过二分查找找到其中一个3 ，那么我们是否能通过二分查找找到firstK和lastK
 *  分析如下：
    
     *  先查找第一个k， 标记位置为position
     *  当地position-1 个位置的值也是k的时候，我们认为k之前还有重复的数字k存在，依然用二分查找继续找 left ~ k-1 位置中的k
     *  持续以上步骤，直到position-1 位置不是k为止，我们得到firstK = position
     *  同理，如果position+1位置也是k，那么我们递归position+1 ~ right的数组中二分查找k，得到lastK
     *  如上我们用纯二分查找的方式找出了lastK，firstK
 *  经如上分析有如下代码：

/** * 查询有序数组中数字k 出现的次数 * * @author liaojiamin * @Date:Created in 16:08 2021/6/24 */
    public class GetNumberOfK { 
    
        public static void main(String[] args) { 
            int[] array = new int[]{ 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 33, 44, 55, 56, 56, 56, 56, 56, 57};
            System.out.println(binarySearchAllK(array, 0));
        }
     /** * 方法三，还是二分查找，分别找出firstK， lastK */
        public static Integer binarySearchAllK(int[] array, int k) { 
            if (array == null || array.length <= 0) { 
                return -1;
            }
            int firstK = binarySearchFirstK(array, 0, array.length - 1, k);
            int lastK = binarySearchLastK(array, 0, array.length - 1, k);
            if (firstK < 0 && lastK < 0) { 
                return -1;
            }
            return lastK - firstK + 1;
        }
    
        /** * 二分查找第一个k */
        public static Integer binarySearchFirstK(int[] array, int left, int right, int k) { 
            if (array == null || left < 0 || right > array.length - 1 || left > right) { 
                return -1;
            }
            int middle = (left + right) / 2;
            if (array[middle] == k) { 
                if (middle - 1 >= left && array[middle - 1] == k) { 
                    return binarySearchFirstK(array, left, middle - 1, k);
                } else { 
                    return middle;
                }
            }
            if (array[middle] < k) { 
                return binarySearchFirstK(array, middle + 1, right, k);
            }
            if (array[middle] > k) { 
                return binarySearchFirstK(array, left, middle - 1, k);
            }
            return -1;
        }
    
        /** * 二分查找最后一个k */
        public static Integer binarySearchLastK(int[] array, int left, int right, int k) { 
            if (array == null || left < 0 || right > array.length - 1 || left > right) { 
                return -1;
            }
            int middle = (left + right) / 2;
            if (array[middle] == k) { 
                if (middle + 1 <= right && array[middle + 1] == k) { 
                    return binarySearchLastK(array, middle + 1, right, k);
                } else { 
                    return middle;
                }
            }
            if (array[middle] > k) { 
                return binarySearchLastK(array, left, middle - 1, k);
            }
            if (array[middle] < k) { 
                return binarySearchLastK(array, middle + 1, right, k);
            }
            return -1;
        }
    }

*  如上实现中firstK，lastK都是使用二分查找在数组中查找，并且二分查找的总量不会大于整个数组的量n，他们两次查询的时间复杂度都是O(logn)，因此总的时间复杂度就是O(logn)，达到了我们优化的目的。

[上一篇：数据结构与算法–最小的k个数][k]  
[下一篇：数据结构与算法–二叉树的深度问题][Link 1]

[k]: https://blog.csdn.net/liaojiamin0102/article/details/117964210
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/118216064