Java C++ 算法題解leetcode1608特殊數(shù)組特征值
更新時間：2022年09月14日 09:07:25 作者：AnjaVon
這篇文章主要為大家介紹了Java C++ 算法題解拓展leetcode1608特殊數(shù)組特征值實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
題目要求
思路一：枚舉 + 二分
- 逐一枚舉值域內(nèi)的所有值，然后二分判斷是否合法。
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;
}
}
- 時間復(fù)雜度：O(n log? n)，排序復(fù)雜度為O(n log? n)，枚舉次數(shù)為值域范圍C=1000，所以找答案的復(fù)雜度為O(C log n)
- 空間復(fù)雜度：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;
}
};
- 時間復(fù)雜度：O(n log ?n)，排序復(fù)雜度為O(n log? n)，枚舉次數(shù)為值域范圍C=1000，所以找答案的復(fù)雜度為O(C log? n)
- 空間復(fù)雜度：O(log? n)
思路二：二分枚舉
二分枚舉+二分判定是否合法；
為了方便把判斷合法單獨寫成函數(shù)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;
}
}
- 時間復(fù)雜度：O(n log? n)，排序復(fù)雜度為O(n log ?n)，二分找答案所以復(fù)雜度為O(log ?C log ?n)
- 空間復(fù)雜度：O(log ?n)
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;
}
};
- 時間復(fù)雜度：O(n log? n)，排序復(fù)雜度為O(n log ?n)，二分找答案所以復(fù)雜度為O(log? C log? n)
- 空間復(fù)雜度：O(log? n)
思路三：倒序枚舉
- 因為值域比較小，所以可以直接從值域最后開始倒著枚舉；
- 預(yù)處理出每個值出現(xiàn)的次數(shù)，然后記錄當前合法合法數(shù)值的數(shù)量與當前數(shù)值進行比較。
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]; // 數(shù)量
if (i == tot)
return i;
}
return -1;
}
}
- 時間復(fù)雜度：O(n+C)
- 空間復(fù)雜度：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;
}
};
- 時間復(fù)雜度：O(n+C)
- 空間復(fù)雜度：O(C)
以上就是Java C++ 算法題解leetcode1608特殊數(shù)組特征值的詳細內(nèi)容，更多關(guān)于Java C++ 算法特殊數(shù)組特征值的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了二叉樹先根（先序）遍歷的改進，有需要的朋友可以參考一下2014-01-01
這篇文章主要介紹了C++將CBitmap類中的圖像保存到文件的方法,涉及C++導(dǎo)出資源文件的實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
這篇文章主要為大家詳細介紹了如何利用Qt實現(xiàn)打開最近文檔功能，并實現(xiàn)基本的新建、打開、保存、退出、幫助等功能，感興趣的可以動手嘗試一下2022-06-06
這篇文章主要為大家詳細介紹了c語言的str函數(shù)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
下面小編就為大家分享一篇C++ 壓縮文件及文件夾方法 使用zlib開源庫，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-03-03
折疊參數(shù)就是一個參數(shù)包, 代表是多個未知,tuple元組就是一個折疊參數(shù)的使用，這篇文章主要介紹了C++?折疊參數(shù)包悄然增強編程效率,需要的朋友可以參考下2023-05-05
本文主要介紹了QT5實現(xiàn)簡單的TCP通信的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習或者工作具有一定的參考學(xué)習價值，需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧2022-05-05
這篇文章主要為大家詳細介紹了C++代碼實現(xiàn)五子棋小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
Qt6提供了很多豐富的多媒體支持類,本文將為大家詳細介紹一下Qt6如何結(jié)合QML實現(xiàn)Windows屏幕錄制功能,文中的示例代碼簡潔易懂,有需要的小伙伴可以參考一下2025-04-04
C++ Boost Serialization庫超詳細獎金額
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標準庫的后備，是C++標準化進程的開發(fā)引擎之一，是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-12-12