Java C++题解leetcode消失的两个数字实例
目录
- 题目要求
- 思路:数学推导
- Java
- C++
- Rust
- 总结
题目要求
思路:数学推导
- 不重复的数组序列可以根据高斯公式计算所有元素的总和:
- 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式。
- 减去当前数组和即可得到缺失数字和sumsumsum;
- 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边:
- 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个;
- 同样利用两个“和”的差值得到;
- 利用sumsumsum即可得到另一个。
- 遍历当前数组中所有小于(或大于)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)
总结
奇妙的难度标记机制之顶多标个中等吧……没有看到时空复杂度的时候第一反应是排序检查标记,被这个思路圈了一会才反应过来数组是无序的,那都无序不重复了就很容易想到用元素和来回减。
以上就是Java C++题解leetcode消失的两个数字实例的详细内容,更多关于Java C++题解消失的两个数字的资料请关注我们其它相关文章!
赞 (0)