每日一题做题记录，参考官方和三叶的题解

题目要求

思路一：枚举 + 二分

• 逐一枚举值域内的所有值，然后二分判断是否合法。

Java

class Solution {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int x = 0; x <= nums[n - 1]; x++) { // 枚举
            int l = 0, r = n -1 ;
            while (l < r) { // 二分
                int m = l + r >> 1;
                if (nums[m] >= x)
                    r = m;
                else
                    l = m + 1;
            }
            if (nums[r] >= x && x == n - r)
                return x;
        }
        return -1;
    }
}

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序复杂度为O(nlog⁡n)O(n\log n)O(nlogn)，枚举次数为值域范围C=1000C=1000C=1000，所以找答案的复杂度为O(Clog⁡n)O(C\log n)O(Clogn)
• 空间复杂度：O(log⁡n)O(\log n)O(logn)

C++

class Solution {
public:
    int specialArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int x = 0; x <= nums[n - 1]; x++) { // 枚举
            int l = 0, r = n -1 ;
            while (l < r) { // 二分
                int m = (l + r) >> 1;
                if (nums[m] >= x)
                    r = m;
                else
                    l = m + 1;
            }
            if (nums[r] >= x && x == n - r)
                return x;
        }
        return -1;
    }
};

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序复杂度为O(nlog⁡n)O(n\log n)O(nlogn)，枚举次数为值域范围C=1000C=1000C=1000，所以找答案的复杂度为O(Clog⁡n)O(C\log n)O(Clogn)
• 空间复杂度：O(log⁡n)O(\log n)O(logn)

思路二：二分枚举

• 二分枚举+二分判定是否合法；
  • 为了方便把判断合法单独写成函数getResgetResgetRes。

Java

class Solution {
    int[] nums;
    public int specialArray(int[] num) {
        this.nums = num;
        Arrays.sort(nums);
        int l = 0, r = nums[nums.length - 1];
        while (l < r) {
            int m = l + r >> 1;
            if (getRes(m) <= m)
                r = m;
            else
                l = m + 1;
        }
        return getRes(r) == r ? r : -1;
    }
    int getRes(int x) {
        int n = nums.length, l = 0, r = n - 1;
        while (l < r) {
            int m = l + r >> 1;
            if (nums[m] >= x)
                r = m;
            else
                l = m + 1;
        }
        return nums[r] >= x ? n - r : 0;
    }
}

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序复杂度为O(nlog⁡n)O(n\log n)O(nlogn)，二分找答案所以复杂度为O(log⁡Clog⁡n)O(\log C\log n)O(logClogn)
• 空间复杂度：O(log⁡n)O(\log n)O(logn)

C++

• 注意全局变量和输入变量需要有差别……

class Solution {
public:
    vector<int> nums;
    int specialArray(vector<int>& num) {
        this->nums = num;
        sort(nums.begin(), nums.end());
        int l = 0, r = nums[nums.size() - 1];
        while (l < r) {
            int m = (l + r) >> 1;
            if (getRes(m) <= m)
                r = m;
            else
                l = m + 1;
        }
        return getRes(r) == r ? r : -1;
    }

    int getRes(int x) {
        int n = nums.size(), l = 0, r = n - 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (nums[m] >= x)
                r = m;
            else
                l = m + 1;
        }
        return nums[r] >= x ? n - r : 0;
    }
};

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序复杂度为O(nlog⁡n)O(n\log n)O(nlogn)，二分找答案所以复杂度为O(log⁡Clog⁡n)O(\log C\log n)O(logClogn)
• 空间复杂度：O(log⁡n)O(\log n)O(logn)

思路三：倒序枚举

• 因为值域比较小，所以可以直接从值域最后开始倒着枚举；
• 预处理出每个值出现的次数，然后记录当前合法合法数值的数量与当前数值进行比较。

Java

class Solution {
    public int specialArray(int[] nums) {
        int[] cnt = new int[1001];
        for (int x : nums)
            cnt[x]++;
        for (int i = 1000, tot = 0; i >= 0; i--) {
            tot += cnt[i]; // 数量
            if (i == tot)
                return i;
        }
        return -1;
    }
}

• 时间复杂度：O(n+C)O(n+C)O(n+C)
• 空间复杂度：O(C)O(C)O(C)

C++

class Solution {
public:
    int specialArray(vector<int>& nums) {
        int cnt[1001];
        memset(cnt, 0, sizeof(cnt));
        for (int x : nums)
            cnt[x]++;
        for (int i = 1000, tot = 0; i >= 0; i--) {
            tot += cnt[i];
            if (i == tot)
                return i;
        }
        return -1;
    }
};

• 时间复杂度：O(n+C)O(n+C)O(n+C)
• 空间复杂度：O(C)O(C)O(C)

总结

简单题结果解法好多也写了好久……

【Rust就偷懒了……】

欢迎指正与讨论！