美文网首页
java-有序数组中指定数字出现的次数

java-有序数组中指定数字出现的次数

作者: android_coder | 来源:发表于2021-05-09 10:56 被阅读0次

    1:时间复杂度为o(N)的情况

     private static int countNumber(int[] array, int number) {
            if (array == null || array.length <= 0) {
                return 0;
            }
            int count = 0;
            for (int i = 0; i < array.length; i++) {
                if (array[i] == number) {
                    count++;
                }
            }
            return count;
        }
    

    这个不符合有序数组的要求,有序数组一般优先考虑到二分查找

    2:时间复杂度o(logN)

    总体的思路是:找到第一个出现的位置,然后从该位置起分别向左和向右查找
    2.1:二分查找

     private static int binarySearch(int[] array, int start, int end, int number) {
            if (array == null || array.length <= 0 || (start == end && array[start] != number)) {
                return 0;
            }
            int middle = (start + end) / 2;
            if (array[middle] > number) {
                binarySearch(array, start, middle -1, number);
            } else if (array[middle] < number) {
                binarySearch(array,  middle + 1, end, number);
            } else {
               return middle;
            }
            return -1;
        }
    

    首先通过二分查找找到第一个出现的位置

    2.2:分别从当前位置向前和向后查找

      private static int findNumberCount(int[] array, int number) {
            if (array== null || array.length <= 0) {
                return 0;
            }
            int pos = binarySearch(array, 0, array.length -1, number);
            if (pos == -1) {
                return 0;
            }
            /* 从第一次的位置分别向前和向后查找*/
            int count = 0;
            for (int i = pos; i > 0 && array[i] == number; i--) {------>向前(左)查找
                count++;
            }
            for (int i = pos + 1; i < array.length && array[i] == number; i++) {---->向后(右)查找
                count++;
            }
            return count;
        }
    

    相关文章

      网友评论

          本文标题:java-有序数组中指定数字出现的次数

          本文链接:https://www.haomeiwen.com/subject/hgymdltx.html