Java?C++題解leetcode消失的兩個數(shù)字實例
更新時間：2022年09月29日 14:51:02 作者：AnjaVon
這篇文章主要介紹了Java?C++題解leetcode消失的兩個數(shù)字實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
題目要求
思路：數(shù)學推導
- 不重復的數(shù)組序列可以根據(jù)高斯公式計算所有元素的總和：
- 用當前數(shù)組長度加上兩個缺失的數(shù)字可以得到所有數(shù)字長度，即可應用公式。
- 減去當前數(shù)組和即可得到缺失數(shù)字和sumsumsum；
- 兩個缺失的數(shù)字分別位于m=sum2m=\frac{sum}{2}m=2sum兩邊：
- 遍歷當前數(shù)組中所有小于（或大于）mmm的值，找到缺失的一個；
- 同樣利用兩個“和”的差值得到；
- 利用sumsumsum即可得到另一個。
- 遍歷當前數(shù)組中所有小于（或大于）mmm的值，找到缺失的一個；
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};
}
}
- 時間復雜度：O(n)
- 空間復雜度：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};
}
};
- 時間復雜度：O(n)
- 空間復雜度：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]
}
}
- 時間復雜度：O(n)
- 空間復雜度：O(1)
總結(jié)
奇妙的難度標記機制之頂多標個中等吧……沒有看到時空復雜度的時候第一反應是排序檢查標記，被這個思路圈了一會才反應過來數(shù)組是無序的，那都無序不重復了就很容易想到用元素和來回減。
以上就是Java C++題解leetcode消失的兩個數(shù)字實例的詳細內(nèi)容，更多關(guān)于Java C++題解消失的兩個數(shù)字的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
如何手動安裝Gradle并配置IDEA使用Gradle構(gòu)建
本文給大家分享手動安裝Gradle并配置IDEA使用Gradle構(gòu)建的步驟,本文給大家介紹的非常詳細,感興趣的朋友一起看看吧2025-04-04
ThreadLocal實例通常是希望將狀態(tài)與線程關(guān)聯(lián)起來的類中的私有靜態(tài)字段，下面通過例子給大家詳細介紹Java中ThreadLocal類型及簡單用法，感興趣的朋友跟隨小編一起看看吧2021-10-10
在實際項目開發(fā)中，有時需要與其他系統(tǒng)進行集成完成相關(guān)業(yè)務功能，這種情況最原始做法是程序內(nèi)部相互調(diào)用，除此之外，還可以用消息服務中間件進行業(yè)務處理，用消息服務中間件處理業(yè)務能夠提升系統(tǒng)的異步通信和擴展解耦能力。Spring Boot對消息服務管理提供了非常好的支持2021-10-10
在Java中,我們可以使用第三方庫來實現(xiàn)文字轉(zhuǎn)語音的功能,本文主要介紹了java文字轉(zhuǎn)語音的實現(xiàn)示例,選擇jacob技術(shù)實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2024-03-03
一文詳解SpringBoot如何優(yōu)雅地實現(xiàn)異步調(diào)用
SpringBoot想必大家都用過，但是大家平時使用發(fā)布的接口大都是同步的，那么你知道如何優(yōu)雅的實現(xiàn)異步呢？這篇文章就來和大家詳細聊聊2023-03-03
Spring Boot中使用Redis和Lua腳本實現(xiàn)延時隊列的方案
通過使用Redis和Lua腳本,可以在Spring Boot環(huán)境中實現(xiàn)一個高效且可靠的延時隊列系統(tǒng),這種方法利用了Redis的有序集合數(shù)據(jù)結(jié)構(gòu)和Lua腳本的原子性操作來確保任務的正確性和一致性,這篇文章主要介紹了Spring Boot中使用Redis和Lua腳本實現(xiàn)延時隊列,需要的朋友可以參考下2024-05-05
Java中的Gradle與Groovy的區(qū)別及存在的關(guān)系
這篇文章主要介紹了Java中的Gradle與Groovy的區(qū)別及存在的關(guān)系,Groovy是一種JVM語言，它可以編譯為與Java相同的字節(jié)碼，并且可以與Java類無縫地互操作,Gradle是Java項目中主要的構(gòu)建系統(tǒng)之一，下文關(guān)于兩者的詳細內(nèi)容，需要的小伙伴可以參考一下2022-02-02
這篇文章主要介紹了JAVA 獲取系統(tǒng)當前時間實例代碼的相關(guān)資料,需要的朋友可以參考下2016-10-10
SpringMVC修改返回值類型后的消息轉(zhuǎn)換器處理方式
這篇文章主要介紹了SpringMVC修改返回值類型后的消息轉(zhuǎn)換器處理方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
idea顯示springboot多服務啟動界面service操作
這篇文章主要介紹了idea顯示springboot多服務啟動界面service操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09