검 지 offer 코드 해석 - 면접 문제 38 숫자 가 정렬 배열 에 나타 난 횟수

제목: 질서 있 는 배열 에서 K 가 나타 난 횟수 를 집계 합 니 다.
분석: 본 문제 의 가장 직관 적 인 사 고 는 바로 배열 을 옮 겨 다 니 며 K 가 나타 난 횟수 를 통계 하면 된다.
이런 방식 의 시간 복잡 도 는 O (n) 이다.다음은 '질서 있 는 배열' 이라는 조건 을 충분히 이용 하여 알고리즘 의 시간 효율 을 높 인 다.
하나의 질서 있 는 배열 에 대해 모든 숫자 K 는 반드시 한데 집중 되 어 있 기 때문에 우리 가 이 그룹의 K 의 머리 와 꼬리 를 찾 으 면 K 가 나타 난 횟수 를 알 수 있다.
이 문 제 는 질서 있 는 배열 에서 어떤 숫자 를 찾 는 것 으로 바 뀌 었 다.
우 리 는 자 연 스 럽 게 2 분 검색 을 생각 했다. 현재 모든 검색 알고리즘 에서 2 분 검색 은 가장 높 은 검색 효율 을 가지 고 있다.
이 문제 에 대해 서 는 두 번 의 2 분 검색 이 필요 하 며, 한 번 은 K 의 머리 를 찾 고, 한 번 은 K 의 꼬리 를 찾 아야 한다.
2 분 K 머리 를 검색 하 는 과정 은 다음 과 같 습 니 다.
1. 현재 배열 의 중심 점 확인 하기;
2. 중심 점
3. 중심 점 > K 라면 K 의 출발점 은 전반 에 있다.
4. 만약 에 중심 점 = K 라면 중심 점 의 앞 점 이 K 와 같 는 지 판단 한다.
  4.1. K 와 같 으 면 K 의 출발점 은 전반 에 있다.
  4.2. K 와 같 지 않 으 면 이 중심 점 은 K 의 출발점 이다.
K 의 종 착 점 을 찾 는 것 은 출발점 을 찾 는 것 과 유사 하 다.이 알고리즘 의 구체 적 인 코드 는 다음 과 같다.

/**
 *   ：         K     。
 * @author       
 * @date 2016 3 25 
 */
public class CountKNumber {
	
	/**
	 *   ：              ，  K       。
	 *            O(n)。        “    ”    ，         。
	 * 
	 *         ，     K        ，           K        K     。
	 *         ：              。
	 *               ，           ，             。
	 *     ，            ，    K  ，    K  。
	 *     K       ：
	 * 1.         ；
	 * 2.   K， K       ；
	 * 4.   =K，              K；
	 * 	4.1.   K， K       ；
	 * 	4.2.    K，      K   。
	 *   K          。
	 * 
	 *           ：
	 */
	
	/**
	 *      K     
	 * @param a   
	 * @param k
	 * @return   K     (  －1      )
	 */
	public static int getKNumber(int[] a,int k){
		//     ：     
		if(a==null || a.length<=0){
			System.out.println("    ！");
			return -1;
		}
		
		//        
		int start = 0;
		//        
		int end = a.length-1;
		
		//K     
		int k_start = -1;
		//K     
		int k_end = -1;
		
		//         0       ，  k     
		while(end-start >= 0){
			//      
			int mid = (start+end)/2;
			
			// a[mid]>k， k       
			if(a[mid]>k){
				end = mid-1;
			}
			// a[mid]= 0){
			//      
			int mid = (start+end)/2;
			
			// a[mid]>k， k       
			if(a[mid]>k){
				end = mid-1;
			}
			// a[mid]