검 지 OFPER - 53 - 1, 숫자 가 정렬 배열 에 나타 난 횟수 (js 실현)

제목.
정렬 배열 에 나타 난 숫자 를 통계 합 니 다. 예 를 들 어 정렬 배열 {1, 2, 3, 3, 3, 4, 5} 과 숫자 3 을 입력 하 십시오. 3 은 이 숫자 에서 4 번 나 왔 기 때문에 출력 4.
사고의 방향
가장 쉬 운 방법 은 첫 번 째 숫자 부터 찾 는 것 이지 만 이런 방법 으로 는 면접 을 통과 할 수 없 을 것 이다.
정렬 배열 인 이상 2 분 으로 찾 는 방식 으로 첫 번 째 K 를 찾 아야 합 니 다.
중간 수 를 찾 을 때마다 K 보다 크 면 앞부분 에서 첫 번 째 K 를 계속 찾 아 K 보다 작 으 면 후반 부 에서 첫 번 째 K 를 계속 찾 아 K 라면 첫 번 째 K 인지 아 닌 지 를 판단 하고, 첫 번 째 K 라면 세 기 를 시작 하고, 그렇지 않 으 면 앞부분 에서 첫 번 째 K 를 찾 아 찾 으 면 세 기 를 시작한다.
function GetNumberOfK(data, k)
{
    // write code here
    if (!data) {
        return 0
    }
    let i = 0
    let j = data.length - 1
    while (i <= j) {
        let mid = Math.floor((i + j) / 2)
        if (data[mid] < k) {
            i = mid + 1
        } else if (data[mid] > k) {
            j = mid - 1
        } else {
            if (mid === 0) {
                let counts = 0
                for (let i = 0; i < data.length; i++) {
                    if (data[i] === k) {
                        counts++
                    } else {
                        break
                    }
                }
                return counts
            } else {
                if (data[mid-1] === k) {
                    j = mid - 1
                } else {
                    let counts = 0
                    for (let i = mid; i < data.length; i++) {
                        if (data[i] === k) {
                            counts++
                        } else {
                            break
                        }
                    }
                    return counts
                }
            }
        }
    }
    return 0
}

좋은 웹페이지 즐겨찾기