[LeetCode][LCR177]撞色搭配——异或消去出现偶数次的相同数字

2024-04-06 18:44

本文主要是介绍[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

思考

  1. 因为这题的要求:时间复杂度 O(n),空间复杂度O(1) ,所以暴力法和哈希表统计法不可行
  2. 另一种想法是双指针法:右指针不断向右移动,当找到与左指针上的值相同的值时,左右指针同时向右移动一位,但是仔细思考可以发现,左指针可能指向右指针已经遍历过的位置,如果使用额外变量记录已经遍历过的位置,那空间复杂度可能达不到O(1)的要求
  3. 其实,这道题的一个特点是,出现偶数次的相同数字不是目标数字,看到这种特点,我们应该想到异或运算:两个相同数字异或结果为0。所以,如果将所有数字异或起来,最后留下的数字就是要找的数字
  4. 这时候出现了一个问题:虽然有配对的数字会被消去,但是撞色的数字通过异或会被杂糅为一个结果,我们需要一个方法将其分开。由异或的特点可知,当两个不相同的数字异或后,结果就是在不相同的位上为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]撞色搭配——异或消去出现偶数次的相同数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/880557

相关文章

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

Java数字转换工具类NumberUtil的使用

《Java数字转换工具类NumberUtil的使用》NumberUtil是一个功能强大的Java工具类,用于处理数字的各种操作,包括数值运算、格式化、随机数生成和数值判断,下面就来介绍一下Number... 目录一、NumberUtil类概述二、主要功能介绍1. 数值运算2. 格式化3. 数值判断4. 随机

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin