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ù)組長度加上兩個(gè)缺失的數(shù)字可以得到所有數(shù)字長度，即可應(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è)中等吧……沒有看到時(shí)空復(fù)雜度的時(shí)候第一反應(yīng)是排序檢查標(biāo)記，被這個(gè)思路圈了一會(huì)才反應(yīng)過來數(shù)組是無序的，那都無序不重復(fù)了就很容易想到用元素和來回減。

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

您可能感興趣的文章:

相關(guān)文章

如何手動(dòng)安裝Gradle并配置IDEA使用Gradle構(gòu)建
本文給大家分享手動(dòng)安裝Gradle并配置IDEA使用Gradle構(gòu)建的步驟,本文給大家介紹的非常詳細(xì),感興趣的朋友一起看看吧
2025-04-04
詳解Java中ThreadLocal類型及簡單用法
ThreadLocal實(shí)例通常是希望將狀態(tài)與線程關(guān)聯(lián)起來的類中的私有靜態(tài)字段，下面通過例子給大家詳細(xì)介紹Java中ThreadLocal類型及簡單用法，感興趣的朋友跟隨小編一起看看吧
2021-10-10
Java Spring Boot消息服務(wù)萬字詳解分析
在實(shí)際項(xiàng)目開發(fā)中，有時(shí)需要與其他系統(tǒng)進(jìn)行集成完成相關(guān)業(yè)務(wù)功能，這種情況最原始做法是程序內(nèi)部相互調(diào)用，除此之外，還可以用消息服務(wù)中間件進(jìn)行業(yè)務(wù)處理，用消息服務(wù)中間件處理業(yè)務(wù)能夠提升系統(tǒng)的異步通信和擴(kuò)展解耦能力。Spring Boot對消息服務(wù)管理提供了非常好的支持
2021-10-10
java文字轉(zhuǎn)語音的實(shí)現(xiàn)示例
在Java中,我們可以使用第三方庫來實(shí)現(xiàn)文字轉(zhuǎn)語音的功能,本文主要介紹了java文字轉(zhuǎn)語音的實(shí)現(xiàn)示例,選擇jacob技術(shù)實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下
2024-03-03
一文詳解SpringBoot如何優(yōu)雅地實(shí)現(xiàn)異步調(diào)用
SpringBoot想必大家都用過，但是大家平時(shí)使用發(fā)布的接口大都是同步的，那么你知道如何優(yōu)雅的實(shí)現(xiàn)異步呢？這篇文章就來和大家詳細(xì)聊聊
2023-03-03
Spring Boot中使用Redis和Lua腳本實(shí)現(xiàn)延時(shí)隊(duì)列的方案
通過使用Redis和Lua腳本,可以在Spring Boot環(huán)境中實(shí)現(xiàn)一個(gè)高效且可靠的延時(shí)隊(duì)列系統(tǒng),這種方法利用了Redis的有序集合數(shù)據(jù)結(jié)構(gòu)和Lua腳本的原子性操作來確保任務(wù)的正確性和一致性,這篇文章主要介紹了Spring Boot中使用Redis和Lua腳本實(shí)現(xiàn)延時(shí)隊(duì)列,需要的朋友可以參考下
2024-05-05
Java中的Gradle與Groovy的區(qū)別及存在的關(guān)系
這篇文章主要介紹了Java中的Gradle與Groovy的區(qū)別及存在的關(guān)系,Groovy是一種JVM語言，它可以編譯為與Java相同的字節(jié)碼，并且可以與Java類無縫地互操作,Gradle是Java項(xiàng)目中主要的構(gòu)建系統(tǒng)之一，下文關(guān)于兩者的詳細(xì)內(nèi)容，需要的小伙伴可以參考一下
2022-02-02
JAVA 獲取系統(tǒng)當(dāng)前時(shí)間實(shí)例代碼
這篇文章主要介紹了JAVA 獲取系統(tǒng)當(dāng)前時(shí)間實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下
2016-10-10
SpringMVC修改返回值類型后的消息轉(zhuǎn)換器處理方式
這篇文章主要介紹了SpringMVC修改返回值類型后的消息轉(zhuǎn)換器處理方式，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2021-09-09
idea顯示springboot多服務(wù)啟動(dòng)界面service操作
這篇文章主要介紹了idea顯示springboot多服務(wù)啟動(dòng)界面service操作，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧
2020-09-09