LeetCode 260. 只出现一次的数字 III 中等

2023-11-10 21:30

本文主要是介绍LeetCode 260. 只出现一次的数字 III 中等,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目 - 点击直达

  • 1. 260. 只出现一次的数字 III 中等
    • 1. 题目详情
      • 1. 原题链接
      • 2. 题目要求
      • 3. 基础框架
    • 2. 解题思路
      • 1. 思路分析
      • 2. 时间复杂度
      • 3. 代码实现

1. 260. 只出现一次的数字 III 中等

1. 题目详情

1. 原题链接

LeetCode 260. 只出现一次的数字 III 中等

2. 题目要求

给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1:
输入:nums = [1,2,1,3,2,5]
输出:[3,5]
解释:[5, 3] 也是有效的答案。

示例 2:
输入:nums = [-1,0]
输出:[-1,0]

示例 3:
输入:nums = [0,1]
输出:[1,0]

提示:
2 < = n u m s . l e n g t h < = 3 ∗ 104 2 <= nums.length <= 3 * 104 2<=nums.length<=3104
− 231 < = n u m s [ i ] < = 231 − 1 -231 <= nums[i] <= 231 - 1 231<=nums[i]<=2311
除两个只出现一次的整数外, n u m s nums nums 中的其他数字都出现两次

3. 基础框架

● Cpp代码框架

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {}
};

2. 解题思路

通过异或把数组 n u m s nums nums分成分别只包含一个只出现一次的数的两个部分,分别对这两个部分异或从而分别得到这两个部分的结果 r e t 1 ret1 ret1 r e t 2 ret2 ret2

1. 思路分析

( 1 ) (1) (1) 如何把这两个只出现一次的不同的数分隔到不同的两部分呢?
突破点就在于,不同的这两个数是不同的 r e t 1 ret1 ret1 r e t 2 ret2 ret2,两个整数的不同表现在bit位至少有1位是不同的,而数组中其他数都是出现两次,通过这个不同的bit位既可以把 r e t 1 ret1 ret1 r e t 2 ret2 ret2分开,也会把 n u m s nums nums中其他的数分开且相同的数一定分在同一组,因为相同的数,bit位一定相同。
( 2 ) (2) (2) 首先对 n u m s nums nums中所有的数进行异或,等价于 r e t 1 ret1 ret1 r e t 2 ret2 ret2异或,结果保存在 o p t R e t optRet optRet中;
( 3 ) (3) (3) 找到 o p t R e t optRet optRet中一个为1的bit位,把该位置对应的下标记录在 i n d e x B i t indexBit indexBit中;
( 4 ) (4) (4) 遍历 n u m s nums nums数组,根据每一个数的 i n d e x B i t indexBit indexBit位置是0还是1进行分组;
( 5 ) (5) (5) 对于分隔的两组来说,分别对每一组中所有元素进行异或,得到的结果就是这一组中唯一出现的数,记录在 r e t 1 ret1 ret1 r e t 2 ret2 ret2中;
( 6 ) (6) (6) 返回结果
如何得到具体的某一位bit位?
比如 n u m b e r = 10 number = 10 number=10,二进制 00000000000000000000000000010010 00000000 00000000 00000000 00010010 00000000000000000000000000010010;
得到第5个bit位,期望第5个bit位是1;
(number >> 4) & 1 :使number右移4个bit位,再与1按位与的结果就是第5个bit位的值;
number右移4个bit位: 00000000000000000000000000000001 00000000 00000000 00000000 00000001 00000000000000000000000000000001
再和1按位与: 00000000000000000000000000000001 00000000 00000000 00000000 00000001 00000000000000000000000000000001

2. 时间复杂度

O ( N ) O(N) O(N)

第一次遍历 n u m s nums nums数组计算所有数异或的结果;
第二次遍历至多32次找到第一个不相等的bit位下标;
第三次遍历 n u m s nums nums数组把数组分成两部分,同时不同组的数之间进行异或,最终得到两个结果;
这三次遍历先后并列进行, 2 ∗ N + 32 2*N+32 2N+32

3. 代码实现

位运算-异或

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {int ret1 = 0, ret2 = 0;// 得到 单独出现的两个不同的数 异或的结果int optRet = 0;for(auto& e : nums){optRet ^= e;}// 找到 tmp中第一个为1的bit位,两个不同的数的该bit位的值一个是1,一个是0// 通过这个bit位,把nums数组的元素可以分成两个部分:// 第一部分,只有一个元素出现一次,其他的元素都出现两次;// 第二部分,只有另一个元素出现一次,另外其他元素的元素都出现两次;// 这样就使得问题简化为分别在两个数组中找到只出现一次的元素了int indexBit = 0;while(indexBit < 32){if(((optRet >> index) & 1) == 1){break;}indexBit++;}// 遍历nums数组,第一部分的元素结果在ret1中// 第二部分的结果记录在ret2中for(auto& e : nums){if(((e >> indexBit) & 1) == 1){ret1 ^= e;}else{ret2 ^= e;}}return vector<int>{ret1, ret2};}
};

哈希映射

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {vector<int> ret;ret.reserve(2);unordered_map<int, int> m;for(auto& e : nums){m[e]++;}for(auto& e : nums){if(m[e] == 1){ret.push_back(e);}}return ret;}
};

T h e The The E n d End End

这篇关于LeetCode 260. 只出现一次的数字 III 中等的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

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

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

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

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

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

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

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

电脑多久清理一次灰尘合? 合理清理电脑上灰尘的科普文

《电脑多久清理一次灰尘合?合理清理电脑上灰尘的科普文》聊起电脑清理灰尘这个话题,我可有不少话要说,你知道吗,电脑就像个勤劳的工人,每天不停地为我们服务,但时间一长,它也会“出汗”——也就是积累灰尘,... 灰尘的堆积几乎是所有电脑用户面临的问题。无论你的房间有多干净,或者你的电脑是否安装了灰尘过滤器,灰尘都

哈希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代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L