소 객 - 검 지 offer 시리즈 문제 풀이: 숫자 가 정렬 배열 에 나타 난 횟수

문제 풀이 과정 을 기록 하 다.소 손님 과 힘 단추 에는 모두 관련 제목 이 있 는데 여 기 는 소 손님 의 제목 설명 을 위주 로 한다.이 시 리 즈 는 기본적으로 python 언어 를 사용 합 니 다.1. 문제 설명: 정렬 배열 에 나타 난 숫자 를 통계 합 니 다.
2. 데이터 구조: 2 분 검색
3. 문제 풀이: 방법 1: 폭력 법 이 널리 퍼 져 있 고 똑 같은 것 을 찾 으 면 누적 1.

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        #   
        count = 0
        for i in range(len(data)):
            if data[i] == k:
                count += 1
        return count

방법 2: 2 차 2 분 찾기 2 분 찾기 템 플 릿 은 소결 시리즈 - 2 분 찾기 템 플 릿 소결 (세 가지: 첫 번 째 기초, 두 번 째 를 파악 하 는 것 을 추천 합 니 다. 세 번 째 는 두 번 째 변형 입 니 다)

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        left, right = 0, len(data) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if data[mid] < k:
                left = mid + 1
            elif data[mid] > k:
                right = mid - 1
            else:
                right = mid - 1
        if left >= len(data) or data[left] != k:
            l = -1
        l = left
        #      
        left, right = 0, len(data) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if data[mid] < k:
                left = mid + 1
            elif data[mid] > k:
                right = mid - 1
            else:
                left = mid + 1
        if right < 0 or data[right] != k:
            r = -1
        r = right
        if l == -1 and r == -1:
            return 0
        return r - l + 1

포장 하여 오른쪽 경 계 를 두 번 찾 아 라.

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        #  
        def find_right(data,k):
            left, right = 0, len(data) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if data[mid] < k:
                    left = mid + 1
                elif data[mid] > k:
                    right = mid - 1
                else:
                    left = mid + 1
            return right
        return find_right(data, k) - find_right(data, k - 1)

4. 복잡 도 분석: 방법 1: 시간 복잡 도 는 모두 O (N) 공간 복잡 도 는 모두 O (1) 방법 2: 시간 복잡 도: O (logN) 공간 복잡 도: O (1)