Java C++ 算法题解leetcode1608特殊数组特征值

题目要求

思路一：枚举 + 二分

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

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(n log⁡ n)，排序复杂度为O(n log⁡ n)，枚举次数为值域范围C=1000，所以找答案的复杂度为O(C log n)

• 空间复杂度：O(log⁡ n))

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(n log ⁡n)，排序复杂度为O(n log⁡ n)，枚举次数为值域范围C=1000，所以找答案的复杂度为O(C log⁡ n)

• 空间复杂度：O(log⁡ n)

思路二：二分枚举

二分枚举+二分判定是否合法；

为了方便把判断合法单独写成函数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(n log⁡ n)，排序复杂度为O(n log ⁡n)，二分找答案所以复杂度为O(log ⁡C log ⁡n)

• 空间复杂度：O(log ⁡n)

C++

• 注意全局变量和输入变量需要有差别&hellip;&hellip;

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(n log⁡ n)，排序复杂度为O(n log ⁡n)，二分找答案所以复杂度为O(log⁡ C log⁡ n)

• 空间复杂度：O(log⁡ n)

思路三：倒序枚举

• 因为值域比较小，所以可以直接从值域最后开始倒着枚举；

• 预处理出每个值出现的次数，然后记录当前合法合法数值的数量与当前数值进行比较。

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(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(C)

来源：https://juejin.cn/post/7142521741795917854