顺序遍历 + 二分查找算法，升序 或 降序 排序，5 解法求解《1608. 特殊数组的特征值》

代码遍历:顺序遍历查找:二分查找排序:升序排序:降序语言:JavaScript语言:Go语言:PHP语言:Python语言:C语言:C++语言:C#语言:TypeScript语言:Java
2022-09-12 03:05:20
顺序遍历 + 二分查找算法，升序 或 降序 排序，lower_bound / bisect_left / sort.Search 枚举 x，5 解法求解《1608. 特殊数组的特征值》

例题

1608. 特殊数组的特征值

给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
注意： x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
示例 1：
输入：nums = [3,5] 输出：2 解释：有 2 个元素（3 和 5）大于或等于 2 。 示例 2： 输入：nums = [0,0]
输出：-1
解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
x 不能取更大的值，因为 nums 中只有两个元素。
示例 3：
输入：nums = [0,4,3,0,4]
输出：3
解释：有 3 个元素大于或等于 3 。
示例 4：
输入：nums = [3,6,7,7,0]
输出：-1
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000

答案

顺序遍历 · 升序

var specialArray = function(nums) {
  const n = nums.length
  nums.sort((a, b) => a - b)
  for (let i = 0; i < n; i++) {
    const x = n - i
    if (nums[i] >= x && (i == 0 || nums[i - 1] < x)) return x
  }
  return -1
};
function specialArray(nums: number[]): number {
  const n = nums.length
  nums.sort((a, b) => a - b)
  for (let i = 0; i < n; i++) {
    const x = n - i
    if (nums[i] >= x && (i == 0 || nums[i - 1] < x)) return x
  }
  return -1
};
class Solution {
  function specialArray($nums) {
    $n = count($nums);
    sort($nums, SORT_NUMERIC);
    foreach ($nums as $i => $num) {
      $x = $n - $i;
      if ($num >= $x && ($i === 0 || $nums[$i - 1] < $x)) return $x;
    }
    return -1;
  }
}
func specialArray(nums []int) int {
  n := len(nums)
  sort.Ints(nums)
  for i := 0; i < n; i++ {
    x := n - i
    if nums[i] >= x && (i == 0 || nums[i - 1] < x) {
      return x
    }
  }
  return -1
}
class Solution {
  public int specialArray(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    for (int i = 0; i < n; i++) {
      int x = n - i;
      if (nums[i] >= x && (i == 0 || nums[i - 1] < x)) return x;
    }
    return -1;
  }
}
public class Solution {
  public int SpecialArray(int[] nums) {
    int n = nums.Length;
    Array.Sort(nums);
    for (int i = 0; i < n; i++) {
      int x = n - i;
      if (nums[i] >= x && (i == 0 || nums[i - 1] < x)) return x;
    }
    return -1;
  }
}
static inline int cmp(const void* pa, const void* pb) {
  return *(int*) pa - *(int*)pb;
}
int specialArray(int* nums, int numsSize){
  qsort(nums, numsSize, sizeof(int), cmp);
  for (int i = 0; i < numsSize; i++) {
    int x = numsSize - i;
    if (nums[i] >= x && (i == 0 || nums[i - 1] < x)) return x;
  }
  return -1;
}
class Solution {
public:
  int specialArray(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    for (int i = 0; i < n; i++) {
      int x = n - i;
      if (nums[i] >= x && (i == 0 || nums[i - 1] < x)) return x;
    }
    return -1;
  }
};
class Solution:
  def specialArray(self, nums: List[int]) -> int:
    n = len(nums)
    nums.sort()
    for i in range(0, n):
      x = n - i
      if nums[i] >= x and (i == 0 or nums[i - 1] < x): return x
    return -1

顺序遍历 · 降序

var specialArray = function(nums) {
  const n = nums.length
  nums.sort((a, b) => b - a)
  for (let i = 0; i < n; i++) {
    const x = i + 1
    if (nums[i] >= x && (i == n - 1 || nums[i + 1] < x)) return x
  }
  return -1
};
function specialArray(nums: number[]): number {
  const n = nums.length
  nums.sort((a, b) => b - a)
  for (let i = 0; i < n; i++) {
    const x = i + 1
    if (nums[i] >= x && (i == n - 1 || nums[i + 1] < x)) return x
  }
  return -1
};
class Solution {
  function specialArray($nums) {
    $n = count($nums);
    rsort($nums, SORT_NUMERIC);
    foreach ($nums as $i => $num) {
      $x = $i + 1;
      if ($num >= $x &&($i == $n - 1 || $nums[$i + 1] < $x)) return $x;
    }
    return -1;
  }
}
func specialArray(nums []int) int {
  n := len(nums)
  sort.Sort(sort.Reverse(sort.IntSlice(nums)))
  for i := 0; i < n; i++ {
    x := i + 1
    if nums[i] >= x && (i == n - 1 || nums[i + 1] < x) {
      return x
    }
  }
  return -1
}
class Solution {
  public int specialArray(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    for (int l = 0, r = n - 1; l < r; l++, r--) {
      int t = nums[l];
      nums[l] = nums[r];
      nums[r] = t;
    }
    for (int i = 0; i < n; i++) {
      int x = i + 1;
      if (nums[i] >= x && (i == n - 1 || nums[i + 1] < x)) return x;
    }
    return -1;
  }
}
public class Solution {
  public int SpecialArray(int[] nums) {
    int n = nums.Length;
    Array.Sort(nums, (a, b) => b - a);
    for (int i = 0; i < n; i++) {
      int x = i + 1;
      if (nums[i] >= x && (i == n - 1 || nums[i + 1] < x)) return x;
    }
    return -1;
  }
}
static inline int cmp(const void* pa, const void* pb) {
  return *(int*) pb - *(int*)pa;
}
int specialArray(int* nums, int numsSize){
  qsort(nums, numsSize, sizeof(int), cmp);
  for (int i = 0; i < numsSize; i++) {
    int x = i + 1;
    if (nums[i] >= x && (i == numsSize - 1 || nums[i + 1] < x)) return x;
  }
  return -1;
}
class Solution {
public:
  int specialArray(vector<int>& nums) {
    sort(nums.begin(), nums.end(), greater<int>());
    int n = nums.size();
    for (int i = 0; i < n; i++) {
      int x = i + 1;
      if (nums[i] >= x && (i == n - 1 || nums[i + 1] < x)) return x;
    }
    return -1;
  }
};
class Solution:
  def specialArray(self, nums: List[int]) -> int:
    n = len(nums)
    nums.sort(reverse = True)
    for i in range(0, n):
      x = i + 1
      if nums[i] >= x and (i == n - 1 or nums[i + 1] < x): return x
    return -1

二分查找 · 升序

var specialArray = function(nums) {
  const n = nums.length
  nums.sort((a, b) => a - b)
  let l = 0, r = n - 1
  while (l <= r) {
    const m = l + r >> 1, x = n - m
    if (nums[m] >= x && (m == 0 || nums[m - 1] < x)) return x
    else if (nums[m] < x) l = m + 1
    else r = m - 1
  }
  return -1
};
function specialArray(nums: number[]): number {
  const n = nums.length
  nums.sort((a, b) => a - b)
  let l = 0, r = n - 1
  while (l <= r) {
    const m = l + r >> 1, x = n - m
    if (nums[m] >= x && (m == 0 || nums[m - 1] < x)) return x
    else if (nums[m] < x) l = m + 1
    else r = m - 1
  }
  return -1
};
class Solution {
  function specialArray($nums) {
    $n = count($nums);
    sort($nums, SORT_NUMERIC);
    $l = 0;
    $r = $n - 1;
    while ($l <= $r) {
      $m = $l + $r >> 1;
      $x = $n - $m;
      if ($nums[$m] >= $x && ($m == 0 || $nums[$m - 1] < $x)) return $x;
      elseif ($nums[$m] < $x) $l = $m + 1;
      else $r = $m - 1;
    }
    return -1;
  }
}
func specialArray(nums []int) int {
  n := len(nums)
  sort.Ints(nums)
  l, r := 0, n - 1
  for l <= r {
    m := (l + r) >> 1
    x := n - m
    if nums[m] >= x && (m == 0 || nums[m - 1] < x) {
      return x
    } else if (nums[m] < x) {
      l = m + 1
    } else {
      r = m - 1
    }
  }
  return -1
}
class Solution {
  public int specialArray(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    int l = 0, r = n - 1;
    while (l <= r) {
      int m = l + r >> 1;
      int x = n - m;
      if (nums[m] >= x && (m == 0 || nums[m - 1] < x)) return x;
      else if (nums[m] < x) l = m + 1;
      else r = m - 1;
    }
    return -1;
  }
}
public class Solution {
  public int SpecialArray(int[] nums) {
    int n = nums.Length;
    Array.Sort(nums);
    int l = 0, r = n - 1;
    while (l <= r) {
      int m = l + r >> 1, x = n - m;
      if (nums[m] >= x && (m == 0 || nums[m - 1] < x)) return x;
      else if (nums[m] < x) l = m + 1;
      else r = m - 1;
    }
    return -1;
  }
}
static inline int cmp(const void* pa, const void* pb) {
  return *(int*) pa - *(int*)pb;
}
int specialArray(int* nums, int numsSize){
  qsort(nums, numsSize, sizeof(int), cmp);
  int l = 0, r = numsSize - 1;
  while (l <= r) {
    int m = l + r >> 1, x = numsSize - m;
    if (nums[m] >= x && (m == 0 || nums[m - 1] < x)) return x;
    else if (nums[m] < x) l = m + 1;
    else r = m - 1;
  }
  return -1;
}
class Solution {
public:
  int specialArray(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size(), l = 0, r = n - 1;
    while (l <= r) {    
      int m = l + r >> 1;
      int x = n - m;
      if (nums[m] >= x && (m == 0 || nums[m - 1] < x)) return x;
      else if (nums[m] < x) l = m + 1;
      else r = m - 1;
    }
    return -1;
  }
};
class Solution:
  def specialArray(self, nums: List[int]) -> int:
    n = len(nums)
    nums.sort()
    l, r = 0, n - 1
    while l <= r:
      m = l + r >> 1
      x = n - m
      if nums[m] >= x and (m == 0 or nums[m - 1] < x): return x
      if nums[m] < x: l = m + 1
      else: r = m - 1
    return -1

二分查找 · 降序

var specialArray = function(nums) {
  const n = nums.length
  nums.sort((a, b) => b - a)
  let l = 0, r = n - 1
  while (l <= r) {
    const m = l + r >> 1, x = m + 1
    if (nums[m] >= x && (m == n - 1 || nums[m + 1] < x)) return x
    else if (nums[m] < x) r = m - 1
    else l = m + 1
  }
  return -1
};
function specialArray(nums: number[]): number {
  const n = nums.length
  nums.sort((a, b) => b - a)
  let l = 0, r = n - 1
  while (l <= r) {
    const m = l + r >> 1, x = m + 1
    if (nums[m] >= x && (m == n - 1 || nums[m + 1] < x)) return x
    else if (nums[m] < x) r = m - 1
    else l = m + 1
  }
  return -1
};
class Solution {
  function specialArray($nums) {
    $n = count($nums);
    rsort($nums, SORT_NUMERIC);
    $l = 0;
    $r = $n - 1;
    while ($l <= $r) {
      $m = $l + $r >> 1;
      $x = $m + 1;
      if ($nums[$m] >= $x && ($m === $n - 1 || $nums[$m + 1] < $x)) return $x;
      elseif ($nums[$m] < $x) $r = $m - 1;
      else $l = $m + 1;
    }
    return -1;
  }
}
func specialArray(nums []int) int {
  n := len(nums)
  sort.Sort(sort.Reverse(sort.IntSlice(nums)))
  l, r := 0, n - 1
  for l <= r {
    m := (l + r) >> 1
    x := m + 1
    if nums[m] >= x && (m == n - 1 || nums[m + 1] < x) {
      return x
    } else if nums[m] < x {
      r = m - 1
    } else {
      l = m + 1
    }
  }
  return -1
}
class Solution {
  public int specialArray(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    for (int l = 0, r = n - 1; l < r; l++, r--) {
      int t = nums[l];
      nums[l] = nums[r];
      nums[r] = t;
    }
    int l = 0, r = n - 1;
    while (l <= r) {
      int m = l + r >> 1;
      int x = m + 1;
      if (nums[m] >= x && (m == n - 1 || nums[m + 1] < x)) return x;
      else if (nums[m] < x) r = m - 1;
      else l = m + 1;
    }
    return -1;
  }
}
public class Solution {
  public int SpecialArray(int[] nums) {
    int n = nums.Length;
    Array.Sort(nums, (a, b) => b - a);
    int l = 0, r = n - 1;
    while (l <= r) {
      int m = l + r >> 1;
      int x = m + 1;
      if (nums[m] >= x && (m == n - 1 || nums[m + 1] < x)) return x;
      else if (nums[m] < x) r = m - 1;
      else l = m + 1;
    }
    return -1;
  }
}
static inline int cmp(const void* pa, const void* pb) {
  return *(int*) pb - *(int*)pa;
}
int specialArray(int* nums, int numsSize){
  qsort(nums, numsSize, sizeof(int), cmp);
  int l = 0, r = numsSize - 1;
  while (l <= r) {
    int m = l + r >> 1;
    int x = m + 1;
    if (nums[m] >= x && (m == numsSize - 1 || nums[m + 1] < x)) return x;
    else if (nums[m] < x) r = m - 1;
    else l = m + 1;
  }
  return -1;
}
class Solution {
public:
  int specialArray(vector<int>& nums) {
    sort(nums.begin(), nums.end(), greater<int>());
    int n = nums.size(), l = 0, r = n - 1;
    while (l <= r) {    
      int m = l + r >> 1;
      int x = m + 1;
      if (nums[m] >= x && (m == n - 1 || nums[m + 1] < x)) return x;
      else if (nums[m] < x) r = m - 1;
      else l = m + 1;
    }
    return -1;
  }
};
class Solution:
  def specialArray(self, nums: List[int]) -> int:
    n = len(nums)
    nums.sort(reverse = True)
    l, r = 0, n - 1
    while l <= r:
      m = l + r >> 1
      x = m + 1
      if nums[m] >= x and (m == n - 1 or nums[m + 1] < x): return x
      if nums[m] < x: r = m - 1
      else: l = m + 1
    return -1

二分查找 · 枚举 x · lower_bound

var specialArray = function(nums) {
  const n = nums.length
  nums.sort((a, b) => a - b)
  let l = 0, r = nums[n - 1]
  while (l <= r) {
    const x = l + r >>> 1
    const m = n - lower_bound(nums, x)
    if (m === x) return x
    if (m < x) r = x - 1
    else l = x + 1
  }
  return -1
};
const lower_bound = (nums, num) => {
  let l = 0, r = nums.length - 1
  while (l <= r) {
    const m = l + r >>> 1
    if (nums[m] >= num) r = m - 1
    else l = m + 1
  }
  return l
}
function specialArray(nums: number[]): number {
  const n = nums.length
  nums.sort((a, b) => a - b)
  let l = 0, r = nums[n - 1]
  while (l <= r) {
    const x = l + r >>> 1
    const cnt = n - lower_bound(nums, x)
    if (cnt === x) return x
    if (cnt < x) r = x - 1
    else l = x + 1 
  }
  return -1
};
const lower_bound = (nums, num) => {
  let l = 0, r = nums.length - 1
  while (l <= r) {
    const m = l + r >>> 1
    if (nums[m] >= num) r = m - 1
    else l = m + 1
  }
  return l
}
func specialArray(nums []int) int {
  n := len(nums)
  sort.Ints(nums)
  l, r := 0, nums[n - 1]
  for l <= r {
    x := (l + r) >> 1
    cnt := n - sort.Search(n, func (i int) bool {
      return nums[i] >= x
    })
    if cnt == x {
      return x
    }
    if cnt < x {
      r = x - 1
    } else {
      l = x + 1
    }
  }
  return -1
}
class Solution {
  function specialArray($nums) {
    $n = count($nums);
    usort($nums, function ($a, $b) {
      return $a > $b;
    });
    $l = 0;
    $r = $nums[$n - 1];
    while ($l <= $r) {
      $x = $l + $r >> 1;
      $cnt = $n - $this->lower_bound($nums, $x);
      if ($cnt === $x) return $x;
      if ($cnt < $x) $r = $x - 1;
      else $l = $x + 1;
    }
    return -1;
  }
  function lower_bound($nums, $num) {
    $l = 0;
    $r = count($nums) - 1;
    while ($l <= $r) {
      $m = $l + $r >> 1;
      if ($nums[$m] >= $num) $r = $m - 1;
      else $l = $m + 1;
    }
    return $l;
  }
}
class Solution {
  public int specialArray(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int l = 0, r = nums[n - 1];
    while (l <= r) {
      int x = l + r >>> 1;
      int cnt = n - lowerBound(nums, x);
      if (cnt == x) return x;
      if (cnt < x) r = x - 1;
      else l = x + 1;
    }
    return -1;
  }
  public int lowerBound(int[] nums, int num) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
      int m = l + r >>> 1;
      if (nums[m] >= num) r = m - 1;
      else l = m + 1;
    }
    return l;
  }
}
public class Solution {
  public int SpecialArray(int[] nums) {
    int n = nums.Length;
    Array.Sort(nums);
    int l = 0, r = nums[n - 1];
    while (l <= r) {
      int x = l + r >> 1;
      int cnt = n - lower_bound(nums, x);
      if (cnt == x) return x;
      else if (cnt < x) r = x - 1;
      else l = x + 1; 
    }
    return -1;
  }
  public int lower_bound(int[] nums, int num) {
    int l = 0, r = nums.Length - 1;
    while (l <= r) {
       int m = l + r >> 1;
       if (nums[m] >= num) r = m - 1;
       else l = m + 1;
    }
    return l;
  }
}
static inline int cmp(const void* pa, const void* pb) {
  return *(int*) pa - *(int*)pb;
}
int lower_bound(int* nums, int num, int numsSize) {
  int l = 0, r = numsSize;
  while (l <= r) {
    int m = l + r >> 1;
    if (nums[m] >= num) r = m - 1;
    else l = m + 1;
  }
  return l;
}
int specialArray(int* nums, int numsSize){
  qsort(nums, numsSize, sizeof(int), cmp);
  int l = 0, r = nums[numsSize - 1];
  while (l <= r) {
    int x = l + r >> 1;
    int cnt = numsSize - lower_bound(nums, x, numsSize);
    if (cnt == x) return x;
    else if (cnt < x) r = x - 1;
    else l = x + 1;
  }
  return - 1;
}
class Solution {
public:
  int specialArray(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size(), l = 0, r = nums.back();
    while (l <= r) {
      int x = l + r >> 1;
      int cnt = n - lower_bound(nums, x);
      if (cnt == x) return x;
      else if (cnt < x) r = x - 1;
      else l = x + 1;
    }
    return -1;
  }
  int lower_bound(vector<int>& nums, int num) {
    int l = 0, r = nums.size();
    while (l <= r) {
      int m = l + r >> 1;
      if (nums[m] >= num) r = m - 1;
      else l = m + 1;
    }
    return l;
  }
};
class Solution(object): # 自行实现
  def specialArray(self, nums):
    n = len(nums)
    nums.sort(cmp = lambda a, b: a - b)
    l, r = 0, nums[n - 1]
    def lowerBound(nums, num):
      l, r = 0, len(nums) - 1
      while l <= r:
        m = l + r >> 1
        if nums[m] >= num: r = m - 1
        else: l = m + 1
      return l 
    while l <= r:
      x = l + r >> 1
      cnt = n - lowerBound(nums, x)
      if cnt == x: return x
      if cnt < x: r = x - 1
      else: l = x + 1
    return -1
class Solution:
  def specialArray(self, nums: List[int]) -> int: # bisect_left
    n = len(nums)
    nums = sorted(nums, key=lambda a: a)
    l, r = 0, nums[n - 1]
    while l <= r:
      x = l + r >> 1
      cnt = n - bisect_left(nums, x)
      if cnt == x: return x
      if cnt < x: r = x - 1
      else: l = x + 1
    return -1

小宇
Github　力扣　M站　全部原创，请勿转载
顺序遍历，用位运算求绝对值，求解《1652. 拆炸弹》
顺序遍历，用位运算 (n >> 31 ^ n) - (n >> 31) 求绝对值，求解《1652. 拆炸弹》
顺序遍历，哈希映射，2 解法求解《1640. 能否连接形成数组》
顺序遍历，哈希映射，2 解法求解《1640. 能否连接形成数组》
递归回溯法，回顾求和与 reduce / array_reduce / Aggregate / accumulate 使用，求解《698. 划分为k个相等的子集》
递归回溯法，回顾求和与 reduce / array_reduce / Aggregate / accumulate 使用，求解《698. 划分为k个相等的子集》