【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法

简介: 【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法

题目链接

LeetCode 面试题 17.19. 消失的两个数字[1]

题目描述

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

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

示例1

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

示例2

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

提示:


题解

位运算

首先将数组里的数再加上  到  中所有的数构成一个更大的集合,那么问题就变成了一个数组里有两个数只出现了一次,其余数都出现了两次,求这两个数是多少?

是不是很熟悉?这其实就是 LeetCode 另一道位运算题目:

LeetCode 面试题56 - I. 数组中数字出现的次数[2]

首先还是常规套路,把所有的数异或起来,得到的值  一定就是出现一次的两个数的异或值。

那么再回顾一道最基本的位运算题:

LeetCode 136. 只出现一次的数字[3]

也就是一个数组里有一个数只出现了一次,其余数都出现了两次,求这个数是多少?这就很简单了,只需要全部异或起来就是这个数的值了。

那么回到本题,有没有办法将这  个数拆分成两个集合,每个集合都满足上面这种最简单的条件(只有一个数出现了一次)呢?

刚刚得到了两个只出现一次数字的异或值  ,那么  中的  就表示了这两个数那一位是不同的。那就很简单了啊,我们把所有  个数那一位是  的归为一个集合,那一位是  的归为一个集合,那么这两个只出现一次的数一定会分属两个不同的集合。而其他出现了两次的数,每个数字都会在同一个集合里。

最后对两个集合分别求异或值,就得到了两个出现一次数的值了。

这里有个关键点,就是按照  某一位为  来划分两个集合,其实取任意一位是  的位都是可以的。但是最简单的方法就是取最低位  ,因为这样可以采用位运算  直接得到。

位运算系列还有一个进阶版:

LeetCode 137. 只出现一次的数字 II[4]

这题就与本题无关了,我们留着下次继续讲。

数学法

首先假设缺失的两个数字为  。

令  为  数组中的元素和, 为  数组中的元素平方和。

再用  到  的元素和减去  就得到了  的值,记为 。用  到  的元素平方和减去  就得到了  的值,记为 。

最后只要解出下面这个二元二次方程组就行了:

用求根公式可以解出两个解是:

其中:

下标哈希

一个很直觉的方法就是,我新开辟一个大小为  的数组,然后把  数组中的元素都放在新数组中下标对应的位置,最后看哪两个位置没有数就行了。但是现在要用原地算法,不允许新开辟空间,那我们就只能直接放在原数组里面了。

首先我们还是得把原数组扩展到大小为 ,也就是在末尾增加  个空间,数字就放 。

然后遍历数组,对于  来说,它的位置上最后放的应该是数字  才对,而  应该被放在下标为  的位置。所以我们把  移动到下标为  的位置上去,但是  位置上的数字怎么办呢?不能直接覆盖,不然就再也无法访问了,所以我们把它移动到下标  的位置就行了。也就是说交换下标  和  位置上的两个数。

那么问题接着来了,位置  上面的数对了,但是位置  上面的数还是错的啊。那么只要继续重复交换操作,直到位置  位置上面的数是  ,或者是  就行了。

最后所有数都摆回正确位置了,再扫描一遍数组,如果  ,就说明  这个数不在数组里。

这个方法理论上适合缺任意  个数,只需要一开始在数组后面补上  个  就行了。

代码

位运算(c++)

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size();
        int x = 0;
        for (auto i : nums) x ^= i;
        for (int i = 1; i <= n+2; ++i) x ^= i;
        int lb = x & -x;
        int y = 0;
        for (auto i : nums) {
            if (i&lb) y ^= i;
        }
        for (int i = 1; i <= n+2; ++i) {
            if (i&lb) y ^= i;
        }
        return {y, y^x};
    }
};

数学法(c++)

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        long n = nums.size()+2;
        long S1 = accumulate(nums.begin(), nums.end(), 0);
        long S2 = 0;
        for (auto x : nums) S2 += x*x;
        long a = n*(n+1)/2-S1;
        long b = n*(n+1)*(2*n+1)/6-S2;
        long x = (a+sqrt(2*b-a*a))/2;
        long y = (a-sqrt(2*b-a*a))/2;
        return {x, y};
    }
};

下标哈希(c++)

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        for (int i = 0; i < 3; ++i) {
            nums.push_back(-1);
        }
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] != -1 && i != nums[i]) {
                swap(nums[i], nums[nums[i]]);
            }
        }
        vector<int> res;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == -1) res.push_back(i);
            if (res.size() == 2) break;
        }
        return res;
    }
};
相关文章
|
25天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
38 1
|
1月前
|
Java 编译器 程序员
Java面试高频题:用最优解法算出2乘以8!
本文探讨了面试中一个看似简单的数学问题——如何高效计算2×8。从直接使用乘法、位运算优化、编译器优化、加法实现到大整数场景下的处理,全面解析了不同方法的原理和适用场景,帮助读者深入理解计算效率优化的重要性。
35 6
|
2月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
2月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
37 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
2月前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
2月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
2月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
93 2
|
3月前
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
1天前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
101 80
|
20天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。