侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【数学】消失的两个数字

GabrielxD
2022-09-26 / 0 评论 / 0 点赞 / 17 阅读 / 628 字 / 正在检测是否收录...

题目

面试题 17.19. 消失的两个数字


给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?

以任意顺序返回这两个数字均可。

示例 1:

输入: [1]
输出: [2,3]

示例 2:

输入: [2,3]
输出: [1,4]

提示:

  • nums.length <= 30000

解题

方法一:数学

思路

由题意:设缺失的两个数分别为 xxyy (x<yx<y),给定数组 nums 长度为 mm 且缺少了 22 个数,那么完整数组的长度 n=m+2n=m+2 其中的元素为 1n1 \sim n

根据 1n1 \sim n 的求和公式可得完整数组中所有数之和为 full=n×n+12full=\frac{n \times {n+1}}{2} ,而现有数组 nums 中数之和为 total=i=0m1nums[i]total = \sum_{i=0}^{m-1}{nums[i]} ,那缺失两数之和 twoSum=x+y=fulltotaltwoSum = x+y = full - total,这时求出其中一个缺失的数另一个数也可求得。

而完整数组中每个数均不相同,也就是说 (令 lower=twoSum2lower = \lfloor \frac{twoSum}{2} \rfloor):x<lowerx < lowery>lowery > lower
那么我们就可以求出 1lower1\sim lower 的和,再拿它减去 i=0k(nums[k]<=lower)nums[i]\sum_{i=0}^{k(nums[k]<=lower)}nums[i] 就能得到较小的一个缺失的数(x),剩下的 y=twoSumxy=twoSum-x

于是返回 x,twoSumx{x, twoSum - x}

参考:【宫水三叶】简单数学运用题 - 消失的两个数字

代码

class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2;
        int full = n * (n + 1) / 2, total = 0;
        for (int num : nums) total += num;
        int twoSum = full - total, lower = twoSum / 2;
        int x = lower * (lower + 1) / 2;
        for (int num : nums) {
            if (num <= lower) x -= num;
        }
        return new int[]{x, twoSum - x};
    }
}
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        int full = n * (n + 1) / 2, total = 0;
        for (int& num : nums) total += num;
        int two_sum = full - total, lower = two_sum / 2;
        int x = lower * (lower + 1) / 2;
        for (int& num : nums) {
            if (num <= lower) x -= num;
        }
        return {x, two_sum - x};
    }
};

时间复杂度:O(n)O(n)
空间复杂度:O(1)O(1)

0

评论区