剑指OfferJZ37：数字在升序数组中出现的次数-java版

浅浅的花香味﹌ 2022-08-31 02:17 63阅读 0赞

### 剑指OfferJZ37：数字在升序数组中出现的次数-java版 ###

*   *   *   *  JZ37:统计一个数字在升序数组中出现的次数

#### JZ37:统计一个数字在升序数组中出现的次数 ####

![在这里插入图片描述][093addd4ea7d70f5f5a78eb09cb16cb6.png]

统计一个数字在升序数组中出现的次数，那么这个数在数组中的排序一定是**连续的**  
**二分查找定义**：它是一种效率较高的查找方法。但是，二分查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

**在排序好的数组中查找数字，可以使用二分法来查找**

**二分查找过程**：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

另外声明一下，计算 mid 时需要技巧**防止溢出，我们不写mid=（left+right）/2，建议写成: mid = left + (right - left) / 2**，偶数的时候：取n/2取整，实际上剩下的序列是 索引为取整左边的序列。

**那么查找一个数字在升序数组中出现的次数步骤：**  
**二分查找这个数（k）在数组中的起始位置和在数组中的结束位置，然后拿 结束位置-开始位置+1 就是这个数在数组中出现的次数**  
二分查找定义左节点l和右节点r（l<r），中间节点mid=l+（r-l）/2，查找区间l~r

**查找起始位置**：拿要查找的数k和中间节点mid指向的数字（这里我们叫它中间数）比较

*  如果中间数等于k，那么看中间数左边一位的数，如果其左边数也与k相同，说明这个中间数不是k的起始位置，那么锁定k的起始位置在l~mid-1区间，如果其左边的数与k不相同，那就说明这个中间数是k的起始位置
 *  如果中间数大于k，说明k的起始位置在1~mid-1区间,在这个区间内重复上述比较步骤
 *  如果中间数小于k，说明k的起始位置在mid+1~r区间,在这个区间内重复上述比较步骤

**查找结束位置**：拿要查找的数k和中间节点mid指向的数字（这里我们叫它中间数）比较

*  如果中间数等于k，那么看中间数右边一位的数，如果其右边数也与k相同，说明这个中间数不是k的结束位置，那么锁定k的结束位置在mid+1~r区间，如果其右边的数与k不相同，那就说明这个中间数是k的结束位置
 *  如果中间数大于k，说明k的结束位置在1~mid-1区间,在这个区间内重复上述比较步骤
 *  如果中间数小于k，说明k的结束位置在mid+1~r区间,在这个区间内重复上述比较步骤

例如：统计数字4在升序数组中出现的次数 1 2 3 4 4 4 5 6 7  
首先查找4在数组内的起始位置，在lr区间内，mid指向的数字=4，再看mid左边的数字也和k相同，说明k的起始位置在lmid-1区间

![在这里插入图片描述][e48a66f10e9be725d3ef41bce5fcdafa.png]

在l~mid-1区间内(图中绿色箭头指向区间），mid=l+（r-l）/2=2, mid指向的数字<4，说明k的起始位置在mid+1~r区间

![在这里插入图片描述][1893881e0232cf2652777e63ce0f7af4.png]

在mid+1~r区间内（图中红色箭头指向区间），mid=l+（r-l）/2=3, mid指向的数字<4，说明k的起始位置在mid+1~r区间（图中紫色位置），此时l和r重合，直接返回l所对应的位置，该位置便是4在数组内的起始位置

![在这里插入图片描述][8eac3f9bc72b0577cf368482c20bd2bb.png]

接着查找4在数组内的结束位置，在lr区间内，mid指向的数字=4，再看mid右边的数字也和k相同，说明k的结束位置在mid+1r区间

![在这里插入图片描述][82308ac4f85c6118e5436557bf7f005a.png]

在mid+1~r区间内(图中绿色箭头指向区间），mid=l+（r-l）/2=5, mid指向的数字>4，说明k的结束位置在l~mid-1区间（图中红色指向位置），此时l和r重合，直接返回l所对应的位置，该位置便是4在数组内的结束位置

![在这里插入图片描述][db474f799eb61b08da73e65796557a54.png]

最后拿 结束位置-开始位置+1 就是4在数组中出现的次数

public class jz37{ 
        //找到一个数在数组中的起始位置
        private int findFirstPosition(int[] array,int k){ //k要统计的数字
            int l=0;//下标
            int r=array.length-1;
            while(l<r){ 
                int mid=l + ((r - l)>>1);//(r - l)>>1 代表 r-l的值右移1位，相当于r-l的值除以2取整，这样写计算效率高
                if(array[mid]==k){ //k等于中间值
                    if(mid-1>=0 && array[mid-1]==k){ 
                        //说明mid当前的位置不是初始位置，k的初始位置在1~mid-1区间
                        r=mid-1;//缩小区间
                    }else { 
                        //就可以说明mid位置的数字就是k的初始位置
                        return mid;
                    }
    
                }else if(array[mid]>k){ //k小于中间值
                    r=mid-1;//k的初始位置在1~mid-1区间
                }else { //k大于中间值
                    l=mid+1;//k的初始位置在mid+1~r区间
                }
            }
            return l;
        }
    
        //找到一个数在数组中的终止位置
        private int findLastPosition(int[] array,int k){ 
            int l=0;
            int r=array.length-1;
            while(l<r){ 
                int mid=l + ((r - l)>>1);//(r - l)>>1 代表 r-l的值右移1位，相当于r-l的值除以2取整，这样写计算效率高
                if(array[mid]==k){ //k等于中间值
                    if(mid+1<array.length && array[mid+1]==k){ 
                        //说明mid当前的位置不是终止位置，k的初始位置在mid+1~r区间
                        l=mid+1;
                    }else { 
                        //就可以说明mid位置的数字就是k的终止位置
                        return mid;
                    }
    
                }else if(array[mid]>k){ //k小于中间值
                    r=mid-1;//k的初始位置在1~mid-1区间
                }else { //k大于中间值
                    l=mid+1;//k的初始位置在mid+1~r区间
                }
            }
            return l;
        }
    
        public int GetNumberOfK(int [] array , int k) { 
            if(array.length==0){ 
                return 0;
            }
            int firstPosition = findFirstPosition(array, k);
            int lastPosition = findLastPosition(array, k);
    
            if(array[firstPosition]!=k){ 
                return 0;
            }
            return lastPosition-firstPosition+1;
        }

![在这里插入图片描述][2a0cd4702def4a7649545421e8fefb53.png]  
![在这里插入图片描述][306b4111d2e14529b4259a9ef58e8d5d.gif_pic_center]

[093addd4ea7d70f5f5a78eb09cb16cb6.png]: /images/20220829/c0865da9d2104906b53833560fd77960.png
[e48a66f10e9be725d3ef41bce5fcdafa.png]: /images/20220829/d4a16dc8f6d8410284488efd2b194891.png
[1893881e0232cf2652777e63ce0f7af4.png]: /images/20220829/acbc4eb7d61244719418056fde273b54.png
[8eac3f9bc72b0577cf368482c20bd2bb.png]: /images/20220829/c9833862822348e7b965cedfcec384ad.png
[82308ac4f85c6118e5436557bf7f005a.png]: /images/20220829/7ada7d54ce654a1daf1458a5098a7877.png
[db474f799eb61b08da73e65796557a54.png]: /images/20220829/8bb35d2d897e44c397f22c4dd444c47a.png
[2a0cd4702def4a7649545421e8fefb53.png]: /images/20220829/e0116a395ecd48c690536d19e20388e8.png
[306b4111d2e14529b4259a9ef58e8d5d.gif_pic_center]: /images/20220829/61346bc66c084eeb8d69d962959eebc5.png