LeetCode 1608. 特殊数组的特征值

1608. 特殊数组的特征值

 

【排序+二分】排序之后对每个i通过二分找到多少个比他大的数。

class Solution {
 
    // 9:51 二分
 
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, left, right;
        for (var i = 1; i <= n; i++) {
            left = 0; right = n - 1;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (nums[mid] >= i) right = mid - 1;
                else left = mid + 1;
            }
            if (n - left == i) return i;
        }
        return -1;
    }
}

class Solution {
public:
 
    // 10:05
 
    int specialArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), left, right;
        for (auto i = 1; i <= n; i++) {
            left = 0, right = n - 1;
            while (left <= right) {
                int mid = (left + right) >> 1;
                if (nums[mid] >= i) right = mid - 1;
                else left = mid + 1;
            }
            if (n - left == i) return i;
        }
        return -1;
    }
};