[LeetCode] 1608. Special Array With X Elements Greater Than or Equal X

https://leetcode.com/problems/special-array-with-x-elements-greater-than-or-equal-x/description/

leetcode - Special Array With X Elements Greater Than or Equal X

문제 유형 : 이진 탐색

문제 난이도 : Easy

 

문제

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.

 

당신은 음이 아닌 정수 배열 Nums를 받는다.

배열의 x개의 숫자가 x보다 크거나 같으면 특별하다고 한다.

x가 배열에 없을 수도 있다.

특별한 배열이면 x를 반환하고, 아니면 -1을 반환하라.

특별한 배열인 경우, 유일한 x가 존재하도록 보장된다.

 

풀이

우선, 배열을 정렬한다.

x를 0부터 시작해서 n, 즉 배열의 요소 수까지 한다.

이진 탐색을 통해서, 적어도 x보다 큰 수들개수를 구한다.

만약 그 인덱스가 x와 같다면, 그 수를 반환한다.

 

반복문이 끝나도록 못 찾았다면, -1을 반환한다.

 

코드

C++

class Solution {
public:
    int count(vector<int>& nums, int x) {
        auto it = lower_bound(nums.begin(), nums.end(), x);
        return distance(it, nums.end());
    }

    int specialArray(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i <= n; i++) {
            if(count(nums, i) == i) return i;
        }
        return -1;
    }
};