本文主要是介绍[LeetCode][LCR177]撞色搭配——异或消去出现偶数次的相同数字,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
LCR 177. 撞色搭配
整数数组
sockets
记录了一个袜子礼盒的颜色分布情况,其中sockets[i]
表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子,每种颜色的袜子均有两只。请设计一个程序,在时间复杂度 O(n),空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。示例 1:
输入:
sockets = [4, 5, 2, 4, 6, 6]
输出:[2,5]
或[5,2]
示例 2:输入:
sockets = [1, 2, 4, 1, 4, 3, 12, 3]
输出:[2,12]
或[12,2]
提示:
- 2 <=
sockets.length
<= 10000
思考
- 因为这题的要求:时间复杂度 O(n),空间复杂度O(1) ,所以暴力法和哈希表统计法不可行
- 另一种想法是双指针法:右指针不断向右移动,当找到与左指针上的值相同的值时,左右指针同时向右移动一位,但是仔细思考可以发现,左指针可能指向右指针已经遍历过的位置,如果使用额外变量记录已经遍历过的位置,那空间复杂度可能达不到O(1)的要求
- 其实,这道题的一个特点是,出现偶数次的相同数字不是目标数字,看到这种特点,我们应该想到异或运算:两个相同数字异或结果为0。所以,如果将所有数字异或起来,最后留下的数字就是要找的数字
- 这时候出现了一个问题:虽然有配对的数字会被消去,但是撞色的数字通过异或会被杂糅为一个结果,我们需要一个方法将其分开。由异或的特点可知,当两个不相同的数字异或后,结果就是在不相同的位上为1,所以我们根据结果,再遍历一次,通过结果进行分类,将所有的数字以这一位数字是否与结果相同分成两组,分别异或,最终那两个撞色的数字就不会被分到同一组,最终也就不会因为异或被杂糅在一起
解法
class Solution {
public:// 寻找数组中出现奇数次的两个数字vector<int> sockCollocation(vector<int>& nums) {int xorResult = 0, bitMask = 1, numA = 0, numB = 0;for(auto &num : nums) xorResult ^= num; // 求出数组中所有数字的异或结果while(!(xorResult & bitMask)) bitMask <<= 1; // 找到异或结果中为1的最低位for(auto &num : nums) {bitMask&num ? numA ^= num : numB ^= num;}// 根据最低位将数字分为两组,并分别进行异或操作return vector<int>{numA, numB}; // 返回结果数组}
};
这篇关于[LeetCode][LCR177]撞色搭配——异或消去出现偶数次的相同数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!