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