Java?C++題解leetcode消失的兩個(gè)數(shù)字實(shí)例

更新時(shí)間：2022年09月29日 14:51:02 作者：AnjaVon

這篇文章主要介紹了Java?C++題解leetcode消失的兩個(gè)數(shù)字實(shí)例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路：數(shù)學(xué)推導(dǎo)

不重復(fù)的數(shù)組序列可以根據(jù)高斯公式計(jì)算所有元素的總和：
- 用當(dāng)前數(shù)組長(zhǎng)度加上兩個(gè)缺失的數(shù)字可以得到所有數(shù)字長(zhǎng)度，即可應(yīng)用公式。
減去當(dāng)前數(shù)組和即可得到缺失數(shù)字和sumsumsum；
兩個(gè)缺失的數(shù)字分別位于m=sum2m=\frac{sum}{2}m=2sum兩邊：
- 遍歷當(dāng)前數(shù)組中所有小于（或大于）mmm的值，找到缺失的一個(gè)；
  - 同樣利用兩個(gè)“和”的差值得到；
- 利用sumsumsum即可得到另一個(gè)。

Java

class Solution {
    public int[] missingTwo(int[] nums) {
        int len = nums.length + 2;
        int tot = len * (1 + len) / 2;
        for (int x : nums)
            tot -= x;
        int sum = tot, m = tot / 2;
        tot = m * (1 + m) / 2;
        for (int x : nums) {
            if (x <= m) // m向下取整，可能相等
                tot -= x;
        }
        return new int[]{tot, sum - tot};
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

C++

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int len = nums.size() + 2;
        int tot = len * (1 + len) / 2;
        for (int x : nums)
            tot -= x;
        int sum = tot, m = tot / 2;
        tot = m * (1 + m) / 2;
        for (int x : nums) {
            if (x <= m) // m向下取整，可能相等
                tot -= x;
        }
        return {tot, sum - tot};
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

Rust

impl Solution {
    pub fn missing_two(nums: Vec<i32>) -> Vec<i32> {
        let len = nums.len() as i32 + 2;
        let mut sum : i32 = nums.iter().sum();
        sum = len * (1 + len) / 2 - sum;
        let m = sum / 2; // m向下取整，可能相等
        let mut lsum : i32 = nums.iter().filter(|&x| x <= &m).sum();
        lsum = m * (1 + m) / 2 - lsum;
        vec![lsum, sum - lsum]
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

總結(jié)

奇妙的難度標(biāo)記機(jī)制之頂多標(biāo)個(gè)中等吧……沒(méi)有看到時(shí)空復(fù)雜度的時(shí)候第一反應(yīng)是排序檢查標(biāo)記，被這個(gè)思路圈了一會(huì)才反應(yīng)過(guò)來(lái)數(shù)組是無(wú)序的，那都無(wú)序不重復(fù)了就很容易想到用元素和來(lái)回減。

以上就是Java C++題解leetcode消失的兩個(gè)數(shù)字實(shí)例的詳細(xì)內(nèi)容，更多關(guān)于Java C++題解消失的兩個(gè)數(shù)字的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章:

相關(guān)文章

Java操作Mongodb數(shù)據(jù)庫(kù)實(shí)現(xiàn)數(shù)據(jù)的增刪查改功能示例
這篇文章主要介紹了Java操作Mongodb數(shù)據(jù)庫(kù)實(shí)現(xiàn)數(shù)據(jù)的增刪查改功能,結(jié)合完整實(shí)例形式分析了java針對(duì)MongoDB數(shù)據(jù)庫(kù)的連接、增刪改查等相關(guān)操作技巧,需要的朋友可以參考下
2017-08-08
Java用鄰接矩陣存儲(chǔ)圖的示例代碼
鄰接矩陣通常采用一個(gè)一維數(shù)組存儲(chǔ)圖中節(jié)點(diǎn)的信息，采用一個(gè)二維數(shù)組存儲(chǔ)圖中節(jié)點(diǎn)之間的鄰接關(guān)系。本文將利用Java實(shí)現(xiàn)用鄰接矩陣存儲(chǔ)圖，需要的可以參考一下
2022-06-06
Spring實(shí)戰(zhàn)之獲取方法返回值操作示例
這篇文章主要介紹了Spring實(shí)戰(zhàn)之獲取方法返回值操作,涉及spring配置文件與方法返回值操作相關(guān)使用技巧,需要的朋友可以參考下
2019-12-12
Java?LocalDateTime常用操作方法
這篇文章主要介紹了Java?LocalDateTime實(shí)用方法,Java8提供了新的時(shí)間接口LocalDateTime，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下
2022-01-01
Java中static與instance的區(qū)別及作用詳解
這篇文章主要為大家介紹了Java中static與instance的區(qū)別及作用詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
2023-07-07
SpringBoot項(xiàng)目請(qǐng)求不中斷動(dòng)態(tài)更新代碼的實(shí)現(xiàn)
在開(kāi)發(fā)中,有時(shí)候不停機(jī)動(dòng)態(tài)更新代碼熱部署是一項(xiàng)至關(guān)重要的功能,它可以在請(qǐng)求不中斷的情況下下更新代碼,這種方式不僅提高了開(kāi)發(fā)效率,還能加速測(cè)試和調(diào)試過(guò)程,本文將詳細(xì)介紹如何在 Spring Boot 項(xiàng)目在Linux系統(tǒng)中實(shí)現(xiàn)熱部署,特別關(guān)注優(yōu)雅關(guān)閉功能的實(shí)現(xiàn)
2024-09-09
JavaFX如何獲取ListView(列表視圖)的選項(xiàng)
這篇文章主要介紹了JavaFX如何獲取ListView(列表視圖)的選項(xiàng),具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2024-01-01
jxl操作excel寫(xiě)入數(shù)據(jù)不覆蓋原有數(shù)據(jù)示例
網(wǎng)上很多例子，都是用Jxl讀或者寫(xiě)excel，本文實(shí)現(xiàn)的功能就是將數(shù)據(jù)源in.xls的第幾行第幾列數(shù)據(jù)寫(xiě)入到out.xls的第幾行第幾列，不覆蓋out.xls其他原有的數(shù)據(jù)。
2014-03-03
Java使用Queryable-pageable實(shí)現(xiàn)分頁(yè)效果
這篇文章主要為大家介紹了Java如何使用Queryable-pageable從而實(shí)現(xiàn)分頁(yè)效果，文中的示例代碼簡(jiǎn)潔易懂，感興趣的小伙伴可以動(dòng)手嘗試一下
2022-06-06
Java?@Autowired報(bào)錯(cuò)原因分析和4種解決方案
這篇文章主要介紹了Java?@Autowired報(bào)錯(cuò)原因分析和4種解決方案，文章圍繞主題展開(kāi)詳細(xì)內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考以一下
2022-05-05