Java中如何实现LeetCode 1608特殊数组特征值的长尾词查找算法？

本文共计1144个文字，预计阅读时间需要5分钟。

目录+主题要求+思路一：列举++二分+Java+C+++思路二：二分列举+Java+C+++思路三：逆序列举+Java+C+++主题要求+思路一：列举++二分+逐一代举值域内的所有值，然后进行二分判断。+Java

目录

• 题目要求
• 思路一：枚举 + 二分
• Java
• C++
• 思路二：二分枚举
• Java
• C++
• 思路三：倒序枚举
• Java
• C++

题目要求

思路一：枚举 + 二分

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

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。

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)

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

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)

思路三：倒序枚举

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

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)

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)

以上就是Java C++ 算法题解leetcode1608特殊数组特征值的详细内容，更多关于Java C++ 算法特殊数组特征值的资料请关注自由互联其它相关文章！