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

本是古典何须时尚 2021-10-26 15:30 366阅读 0赞

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

两种常见解法：

1.  遍历一遍数组，进行查找，这个方法没有利用**排序数组**这个条件。时间复杂度较高  
    **时间复杂度：O(n)**
    
        //一层循环遍历数组，省略
    
    2.利用**排序数组**这个条件，通过二分法来找到，找到第一个k的索引和最后一个数组的索引。  
    **时间复杂度：O(logn)**
    
        public int GetNumberOfK(int [] array , int k) { 
            	if(array == null || array.length ==0)
            		return 0;
            	int firstIndex = getKIndex(array, k, 0, array.length-1, 1);
            	int lastIndex = getKIndex(array, k, 0, array.length-1, 0);
            	if(firstIndex==-1 || lastIndex==-1)
            		return 0;
            	return lastIndex-firstIndex+1;
            }
        
        	private int getKIndex(int[] array, int k, int low, int high, int isFirst) { 
        		int middleIndex = (low+high)/2;
        		int middleValue = array[middleIndex];
        		int newLow = low;
        		int newHigh = high;
        		if(low>high) { 
        			return -1;
        		}
        		if(k==middleValue) { 
        			if(isFirst == 0) { 
        			if(middleIndex == array.length-1 || array[middleIndex+1] != k)
        				return middleIndex;
        			newLow = middleIndex +1;
        			}
        			else { 
        				if(middleIndex == 0 || array[middleIndex-1] != k)
        					return middleIndex;
        				newHigh = middleIndex -1;
        			}
        		}
        		else if(k<middleValue) { 
        			newHigh = middleIndex - 1;
        		}
        		else { 
        			newLow = middleIndex + 1;
        		}
        		return getKIndex(array, k, newLow, newHigh, isFirst);
        	
        	}