要成功就做一百题-95

题目名称

已经排序的数组，必须在O(logn)的复杂度下统计得到指定元素的重复次数。

描述

比如数组[1,1,2,2,2,3,4,4,4,4,5,7,19]，其中4重复4次。

解题思路

如果不要求logn的复杂度，可以二分查到目标值相等某个位置，然后分别向两边统计，得到最终的结果。但要求logn的情况下，必须要全局都是二分的操作。排除向两边分别查找的方法，可以看到目标是数组中的一个范围。所以可以先找左边，再找右边；之前是遇到相等就返回，现在需要额外再加限制条件，先从左边开始，如果找到了相等的位置，而且该位置左边的值，即mid-1的位置小于目标值，则是重复元素区间的最左开始，这里注意也包括索引位0的位置，即数组最左边；否则，就从end = mid-1的位置往左找，找到索引位0的位置结束，最终就是重复元素区间最左侧；
现在回到右边，只是截止条件包括了mid == arr.length - 1的情况。找的时候是从start = mid + 1的位置开始。如下是代码。

代码

    @Test
    public void test(){
        int[] arr = new int[]{1,1,1,2,2,2,3,4,4,4,5,6};
        int key = 3;

        System.out.println(bsRangeLeft(arr,key));
        System.out.println(bsRangeRight(arr, key));
        System.out.println(rangeSize(arr,key));
    }

    private int rangeSize(int[] arr, int key){
        if(null == arr || arr.length == 0){
            return -1;
        }
        int l = bsRangeLeft(arr, key);
        int r = bsRangeRight(arr, key);
        if(l == r && l < 0){
            return -1;
        }else {
            return Math.abs(r - l) + 1;
        }
    }
   //找左边索引位置
    private int bsRangeLeft(int[] arr, int key){
        int start = 0;
        int end = arr.length - 1;
        int mid;
        while (start <= end){
            mid = start + (end - start)/2;
            if(key == arr[mid]){
                if(mid == 0 || arr[mid - 1] < key){
                   //找到直接返回，条件是已经是最左边或者左边隔一位的值比目标小。
                    return mid;
                }
                end = mid - 1;
             //从mid-1的位置往前找
            }else if(key > arr[mid]){
                start = mid + 1;
            }else if(key < arr[mid]){
                end = mid -1;
            }
        }
        return -1;
    }

    private int bsRangeRight(int[] arr, int key){
        int start = 0;
        int end = arr.length - 1;
        int mid;
        while (start <= end){
            mid = start + (end - start)/2;
            if(key == arr[mid]){
                if(mid == arr.length -1 || arr[mid+1] > key){
                    return mid;//已经到最右边最大值或者它的右边一个比目标值大
                }
                start = mid + 1;//从mid+1的位置往右找
            }else if(key > arr[mid]){
                start = mid + 1;
            }else if(key < arr[mid]){
                end = mid - 1;
            }
        }
        return -1;
    }

总结

O(n)和O(logn)还是有区别的，一是一，二是二，鸡蛋没有鹅蛋大。