剑指Offer-数字在排序数组中出现的次数

╰+攻爆jí腚メ 2022-02-19 06:15 178阅读 0赞

## 题目描述 ##

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

解题思路—**二分查找**：不要拿到题目就想着循环遍历数组判断大小，一定要有这个意识，**题目提到有序数列，就想到二分**！通过二分查找找到数字在数组中的**起始点和截止点**，然后**相减**得到次数。编写代码的时候要**注意二分查找数组的上下界start和end，是会随着每一次递归或者循环变化的**！还有特别使用**循环写二分查找**时，要**注意将中值middle放入循环中**，要不然middle不会变！

## Java解题—二分查找 ##

public class Solution {
        public int GetNumberOfK(int [] array , int k) {
           if(array.length==0)
                return 0;
    
            int firstK = getFirst(array, k,0, array.length-1);
            int lastK = getLast(array, k, 0, array.length-1);
    
            if(firstK!=-1 && lastK!=-1)
                return lastK-firstK+1;
            return 0;
        }
        
        public int getFirst(int[] array, int k, int start, int end){
            if(start>end)
                return -1;
            int middle = (start+end)/2;
    
            if(array[middle]>k)
                return getFirst(array, k, start, middle-1);
            else if(array[middle]<k)
                return getFirst(array, k, middle+1, end);
            else if(middle-1 >= start && array[middle-1]==k)  // 这里要注意是start，而不是0
                return getFirst(array, k, start, middle-1);
            else
                return middle;
        }
        
    	// 使用循环
        public int getLast(int[] array, int k, int start, int end){
            if(start>end)
                return -1;
            
            while(start<=end){
                int middle = (start+end)/2; // middle要放入循环中
                if(array[middle]>k)
                    end = middle - 1;
                else if(array[middle]<k)
                    start = middle + 1;
                else if(middle+1<=end && array[middle+1]==k) // 这里要注意是end，而不是array.length
                    start = middle + 1;
                else
                    return middle;
            }
            return -1;
        }
    }