OFFER - 정렬 배열에 숫자가 나타나는 횟수

Question

Solution

절반으로 찾기

Question

하나의 숫자가 정렬 수조에 나타나는 횟수를 통계하다.키워드: 질서수 그룹 횟수 반으로 찾기

Solution

반으로 접어서 같은 숫자를 찾아 앞뒤로 세어라.

반값으로 찾다

시간 복잡도: O (N)?공간 복잡성: O(1)

Python

class Solution:
    def GetNumberOfK(self, data, k):
        count = 0
        l = 0
        r = len(data)-1
        while l<=r:
            mid = (l+r)//2
            if data[mid]==k:
                count = 1
                low = mid-1
                hi = mid+1
                while low>=0 and data[low]==k:
                    count += 1
                    low -= 1
                while hi<len(data) and data[hi]==k:
                    count += 1
                    hi += 1
                break
            elif data[mid]>k:
                r = mid-1
            else:
                l = mid+1
        return count

C++

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int l = 0;
        int r = data.size()-1;
        int count = 0;
        while(l<=r){
            int mid = (l+r)/2;
            if (data[mid]==k){
                count = 1;
                int low = mid-1;
                int hi = mid+1;
                while(low>=0 && data[low]==k){
                    count++;
                    low--;
                }
                while(hi<data.size() && data[hi]==k){
                    count++;
                    hi++;
                }
                break;
            }
            else if(data[mid] > k)
                r = mid-1;
            else
                l = mid+1;
        }
        return count;
    }
};