【leetcode】【2022/9/12】1608. 特殊数组的特征值

问题描述：

• 给你一个非负整数数组 nums。如果存在一个数 x，使得 nums 中恰好有 x 个元素大于或者等于 x，那么就称 nums 是一个特殊数组，而 x 是该数组的特征值。
• 如果数组 nums 是一个特殊数组，请返回它的特征值 x，否则返回 -1。
  • 可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是唯一的。

核心思路：

• 第一反应确实是排序 + 枚举。
  • 降序排序后，一次遍历，遍历过程中当前索引 i 如果是特征值，则满足 nums[i-1] >= i and nums[i] < i。【注意 i 从 1 开始】
• 更好的方法是排序后进行二分找到合适的位置即可。【合适的位置同样满足上式】

代码实现：

• 模拟解法代码实现如下：

  class Solution
  {
  public:
      int specialArray(vector<int>& nums)
      {
          sort(nums.begin(), nums.end(), greater<int>());
          int m = nums.size();
          for(int i = 1; i <= m; ++i)
          {
              // 满足 nums[i-1] >= i and nums[i] < i
              if(nums[i-1] >= i and (i == m or nums[i] < i))
                  return i;
          }
          return -1;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16

• 二分解法代码实现如下：

  class Solution
  {
  public:
      int specialArray(vector<int>& nums)
      {
          sort(nums.begin(), nums.end());
          int n = nums.size(), left = 1, right = nums.size();
          while (left <= right)
          {
              int mid = left + right >> 1;
              if (nums[n - mid] >= mid)
              {
                  if (mid == n || nums[n - mid - 1] < mid)
                      return mid;
                  else
                      left = mid + 1;
              }
              else
                  right = mid - 1;
          }
          return -1;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23