[LeetCode] 1287. Element Appearing More Than 25% In Sorted Array

https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/description/

Element Appearing More Than 25% In Sorted Array - LeetCode

leetcode - Element Appearing More Than 25% In Sorted Array

문제 유형: 배열, 구현, 슬라이딩 윈도우

문제 난이도: Easy

 

문제

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.

 

비내림차순으로 정렬된 정수 배열이 있다. 정확히 한 정수가 25%가 넘게 있다.

그 정수를 반환하시오.

 

 

풀이

정렬되어있는 배열에서 하나씩 탐색해나가면서 각 요소별로 스트릭을 갱신해보면서 25%가 넘으면 그 수를 반환하면 된다.

 

 

코드

C++

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        const int n = arr.size();
        int streak = 1;

        for(int i = 1; i < n; i++) {
            if(arr[i] == arr[i-1]) streak++;
            else streak = 1;
            if(streak > n/4) return arr[i];
        }
        return arr[0];
    }
};