剑指offer----数字在排序数组中出现的次数----java实现

系统管理员 2022-07-21 00:09 81阅读 0赞

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

因为是排序数组，那么数组中第一个K之前的数都会比K小，最后一个K之后的数都会比K大，可以分为两步来解决这个问题，分别用二分查找找到数组中第一个K再找到第二个K，这样就可以得到数组中K的个数。

在数组中查找K，如果中间的数比K大，那么K出现在前半段；

如果比K小，K出现在后半段，那么K出现在后半段；

如果等于K，寻找第一个K的算法则需要判断K的前一个数和K的大小或者是否已经到达数组的起始位置：

1）等于K的话，则第一个K还在半段，

2）如果不等于K，则K是第一个K；

寻找最后一个K的算法，则需要和K后面的一个数进行比较，或者是否已经到达数组的终止位置

1）等于K的话，则最后一个K还在后半段

2）不等于K的话，则这个K就是最后一个K

代码：

public class Solution {
        public int GetNumberOfK(int [] array , int k) 
        {
           int number = 0;
    		if(array !=null)
    		{
    		   int first = getFirstK(array,k,0,array.length-1);//调用方法得到第一个k的位置
    		   int last = getLastK(array,k,0,array.length -1);//调用方法得到最后一个k的位置
    		   if(first > -1 && last > -1)
    			{
    				number = last - first + 1;//得到k的个数
    			}
    		}
    		
    		return number;
        }
         private int getFirstK(int[]array,int k,int start,int end)
        {
        	if(start > end)
        	{
        		return -1;
        	}
        	int midIndex = (start + end) / 2; //二分查找的中间位置
        	int midData = array[midIndex] ;
        	//当中间位置等于K时
        	if(midData == k)
        	{
        		//判断中间位置的前一个数是不是等于K，不等于k则是第一个k，还需要判断此时有没有到达了数组的起始位置
        		if((midIndex > 0 && array[midIndex-1]!=k)|| midIndex == 0)
        		{
        			return midIndex;
        		}
        		else
        		{
        			end = midIndex - 1;//如果要是等于k的话，则第一个k还在前半段
        		}
        	}
        	else if(midData > k) //中间的数如果大于k，则k在前半段，
        	{
        		end = midIndex -1;
        	}
        	else   //中间的数小于k,则k在后半段
        	{
        		start = midIndex + 1;
        	}
        	return getFirstK(array,k,start,end);
        }
        private int getLastK(int[]array,int k,int start,int end)
        {
        	if(start > end)
        		return -1;
        	int midIndex = (start + end) / 2;
        	int midData = array[midIndex];
        	
        	if(midData == k)
        	{
        		if((midIndex < array.length - 1 && array[midIndex + 1] != k) || midIndex == array.length -1)
        		{
        			return midIndex;
        		}
        		else
        		{
        			start = midIndex + 1;
        		}
        	}
        	else if(midData > k)
        	{
        		end = midIndex - 1;
        	}
        	else
        	{
        		start = midIndex + 1;
        	}
        	
        	return getLastK(array,k,start,end);
        }
    }