면접 문제 53: 정렬 배열 에서 숫자 찾기

제목: 정렬 배열 에 숫자 가 나타 나 는 횟수
정렬 배열 에 나타 난 숫자 를 집계 합 니 다.예 를 들 어 {1, 2, 3, 3, 3, 4, 5} 과 숫자 3 을 입력 하면 3 이 이 배열 에서 4 번 나 왔 기 때문에 4 를 출력 합 니 다.
사고방식: 2 점 찾기 를 개선 하고 다음 에 우 리 는 2 점 찾기 알고리즘 을 어떻게 잘 활용 할 것 인 가 를 생각한다.우리 가 숫자 k 가 정렬 배열 에 나타 난 횟수 를 통계 한다 고 가정 합 니 다.앞의 알고리즘 에서 시간 은 주로 중복 되 는 숫자의 첫 번 째 k 와 마지막 k 의 위 치 를 어떻게 확정 하 는 지 에 소모 되 는데 2 분 검색 알고리즘 으로 첫 번 째 k 와 마지막 k 를 직접 찾 을 수 있 습 니까?우 리 는 먼저 어떻게 2 분 검색 알고리즘 으로 배열 에서 첫 번 째 k 를 찾 는 지 분석 합 니 다.2 분 검색 알고리즘 은 항상 배열 중간의 숫자 와 k 를 비교 합 니 다.만약 중간 숫자 가 k 보다 크다 면 k 는 배열 의 전반 에 만 나타 날 수 있 고 다음 라운드 에 우 리 는 배열 의 전반 에서 만 찾 으 면 된다.만약 에 중간 숫자 가 k 보다 작다 면 k 는 배열 의 후반 부 에 만 나타 날 수 있 고 다음 라운드 에 우 리 는 배열 의 후반 부 에서 만 찾 으 면 된다.중간 숫자 가 k 와 같다 면?우 리 는 먼저 이 숫자 가 첫 번 째 k 인지 아 닌 지 를 판단 한다.중간 숫자 앞 에 있 는 숫자 가 k 가 아니라면 중간 숫자 가 바로 첫 번 째 k 입 니 다.만약 에 중간 숫자의 앞 숫자 도 k 라면 첫 번 째 k 는 배열 의 앞 부분 에 있 을 것 이 고 다음 라운드 에 우 리 는 배열 의 앞 부분 에서 찾 아야 한다.
이상 의 사고방식 을 바탕 으로 자바 참고 코드 는 다음 과 같다.

package chapter6;

public class P263_NumberOfK {//     
    public static int findnumbersofk(int[] data,int target){
        int left=0,right=data.length-1;
        int[] res=new int[2];
        while (left0&&arr[mid-1]!=target||mid==0){
                    return mid;
                }else {
                    right=mid-1;
                }
            }else if(arr[mid]>target){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return -1;
    }

    public static int getLast(int[] arr,int target){//           
        int left=0,right=arr.length-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            if(arr[mid]==target){
                if(midtarget){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return -1;
    }
    public static int findnumbersofk2(int[] arr,int target){//           
        if(arr==null||arr.length<1) return -1;
        int start=getFirst(arr,target);
        int end=getLast(arr,target);
        if(start==-1||end==-1) return 0;
        return end-start+1;
    }
    public static void main(String[] args){
        int target=3;
        int[] data={1,2,3,3,3,3,4,5};
        int[] data1={1,2,4,5};
        int[] data2={3,3,3,3,3,3};
        System.out.println(findnumbersofk(data,target));
        System.out.println(findnumbersofk(data1,target));
        System.out.println(findnumbersofk(data2,target));

        System.out.println(findnumbersofk2(data,target));
        System.out.println(findnumbersofk2(data1,target));
        System.out.println(findnumbersofk(data2,target));
    }
}

테스트 사례: a. 기능 테스트 (배열 에 찾 을 숫자 가 포함 되 어 있 습 니 다. 배열 에 찾 을 숫자 가 없습니다. 찾 을 숫자 는 배열 에 한 번 또는 여러 번 나타 납 니 다).b. 경계 값 테스트 (배열 의 최대 값, 최소 값 을 찾 습 니 다. 배열 에 숫자 가 하나 밖 에 없습니다).c. 특수 입력 테스트 (배열 의 지침 은 nullptr 지침 임 을 나타 낸다).참고:https://www.jianshu.com/p/a5bda52fe134 http://www.cnblogs.com/grandyang/p/4409379.html