欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java C++ 算法題解leetcode1608特殊數(shù)組特征值

 更新時(shí)間:2022年09月14日 09:07:25   作者:AnjaVon  
這篇文章主要為大家介紹了Java C++ 算法題解拓展leetcode1608特殊數(shù)組特征值實(shí)例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

題目要求

思路一:枚舉 + 二分

  • 逐一枚舉值域內(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;
    }
}
  • 時(shí)間復(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;
    }
};
  • 時(shí)間復(fù)雜度:O(n log ?n),排序復(fù)雜度為O(n log? n),枚舉次數(shù)為值域范圍C=1000,所以找答案的復(fù)雜度為O(C log? n)
  • 空間復(fù)雜度:O(log? n)

思路二:二分枚舉

二分枚舉+二分判定是否合法;

為了方便把判斷合法單獨(dú)寫成函數(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;
    }
}
  • 時(shí)間復(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;
    }
};
  • 時(shí)間復(fù)雜度:O(n log? n),排序復(fù)雜度為O(n log ?n),二分找答案所以復(fù)雜度為O(log? C log? n)
  • 空間復(fù)雜度:O(log? n)

思路三:倒序枚舉

  • 因?yàn)橹涤虮容^小,所以可以直接從值域最后開始倒著枚舉;
  • 預(yù)處理出每個(gè)值出現(xiàn)的次數(shù),然后記錄當(dāng)前合法合法數(shù)值的數(shù)量與當(dāng)前數(shù)值進(jì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]; // 數(shù)量
            if (i == tot)
                return i;
        }
        return -1;
    }
}
  • 時(shí)間復(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;
    }
};
  • 時(shí)間復(fù)雜度:O(n+C)
  • 空間復(fù)雜度:O(C)

以上就是Java C++ 算法題解leetcode1608特殊數(shù)組特征值的詳細(xì)內(nèi)容,更多關(guān)于Java C++ 算法特殊數(shù)組特征值的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C語言實(shí)現(xiàn)哈希搜索算法及原理詳解

    C語言實(shí)現(xiàn)哈希搜索算法及原理詳解

    本文主要介紹了C語言實(shí)現(xiàn)哈希搜索算法及原理詳解,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-06-06
  • C語言qsort函數(shù)使用方法詳解

    C語言qsort函數(shù)使用方法詳解

    qsort是一個(gè)庫函數(shù),基于快速排序算法實(shí)現(xiàn)的一個(gè)排序的函數(shù),下面這篇文章主要給大家介紹了關(guān)于C語言qsort()函數(shù)使用的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-09-09
  • C語言實(shí)現(xiàn)放煙花的程序

    C語言實(shí)現(xiàn)放煙花的程序

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)放煙花的程序,有音樂播放,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-02-02
  • 用VC++6.0的控制臺(tái)實(shí)現(xiàn)2048小游戲的程序

    用VC++6.0的控制臺(tái)實(shí)現(xiàn)2048小游戲的程序

    本文是作者拜讀劉地同學(xué)的《C語言控制臺(tái)版2048》之后感覺非常不錯(cuò),添加了注釋之后分享給大家的,方便更多的初學(xué)者閱讀學(xué)習(xí),有需要的小伙伴參考下。
    2015-03-03
  • c語言 字符串轉(zhuǎn)大寫的簡單實(shí)例

    c語言 字符串轉(zhuǎn)大寫的簡單實(shí)例

    這篇文章主要介紹了c語言 字符串轉(zhuǎn)大寫的簡單實(shí)例,有需要的朋友可以參考一下
    2013-12-12
  • opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果

    opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果

    這篇文章主要為大家詳細(xì)介紹了opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • 如何實(shí)現(xiàn)循環(huán)隊(duì)列

    如何實(shí)現(xiàn)循環(huán)隊(duì)列

    本文主要介紹了C語言循環(huán)隊(duì)列的實(shí)現(xiàn),對(duì)于數(shù)據(jù)結(jié)構(gòu)與算法的研究有所幫助,需要的朋友可以參考下
    2015-07-07
  • C++?JSON庫?nlohmann::basic_json::accept的用法解析

    C++?JSON庫?nlohmann::basic_json::accept的用法解析

    nlohmann::basic_json::accept 是 Nlohmann JSON 庫中的一個(gè)方法,它用于檢查一個(gè)字符串是否可以解析為有效的 JSON,這篇文章主要介紹了C++?JSON庫nlohmann::basic_json::accept的用法,需要的朋友可以參考下
    2023-06-06
  • C++超詳細(xì)講解逗號(hào)操作符

    C++超詳細(xì)講解逗號(hào)操作符

    使用逗號(hào)運(yùn)算符是為了把幾個(gè)表達(dá)式放在一起。整個(gè)逗號(hào)表達(dá)式的值為系列中最后一個(gè)表達(dá)式的值。從本質(zhì)上講,逗號(hào)的作用是將一系列運(yùn)算按順序執(zhí)行
    2022-05-05
  • C/C++通過HTTP實(shí)現(xiàn)文件上傳與下載的示例詳解

    C/C++通過HTTP實(shí)現(xiàn)文件上傳與下載的示例詳解

    WinInet是 Microsoft Windows 操作系統(tǒng)中的一個(gè) API 集,用于提供對(duì) Internet 相關(guān)功能的支持,它包括了一系列的函數(shù),使得 Windows 應(yīng)用程序能夠進(jìn)行網(wǎng)絡(luò)通信、處理 HTTP 請(qǐng)求、FTP 操作等,本文給大家介紹了C/C++通過HTTP實(shí)現(xiàn)文件上傳與下載,需要的朋友可以參考下
    2023-12-12

最新評(píng)論