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

2024-02-12 16:48
文章标签 leetcode iii 一次 数字 260

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

文章目录

  • 题目描述
  • 思路分析
    • 简化模型,分析实质
    • 回归问题,拓展应用
  • 代码展示

题目描述

给定一个整数数组 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]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number-iii

思路分析

对于此类问题,我们首先应该想到的就是一个非常实用的操作符‘^’,异或操作!

对于异或操作在这里做出以下基本介绍:

    int a = 10;int b = 10;int c = a^b;//0

① 对于a,b两个变量,初始值一致时,对他们做异或运算结果为零!
② 异或运算满足交换律,结合律。
即 a^b = b^a
a^b ^c = (a^b) ^c = a^ (b^c)
③ 0异或任意数结果为任意数

简化模型,分析实质

现在我们思考一个比较简单的问题:

如果说对于一个整形数组nums,其中只有1个数据出现一次,其余均出现两次,也就是说,我们对数组中所有数据进行异或操作,最终的结果就是两、这个只出现一次的数据。(原因:根据上面介绍的三条异或基本性质可以得出:相同数据异或均为0,最后结果就是0与只出现一次的数据进行异或,结果就是我们要找的数据!!)

下面画个简图作为详细说明:
在这里插入图片描述
上图阐述了循环具体过程以及最终结果。

回归问题,拓展应用

反过来看看数组中有两个不同元素能不能运用同样的方法??
首先分析一下:我们对数组所有元素做异或运算,结果是什么呢??很显然,就是数组中两个只出现一次的数据异或的结果!
也就是说我们这样得到的数据是两个只出现一次数的异或,而并非两个数。这与我们期望的结果不一致。那该怎么办呢??

我们回到异或运算的本质:异或运算是对两个数据的逐比特位进行异或,相同为0,不同为1

那么我们对于两个不同数异或后的结果进行分析:
例如:
8的二进制表达为0000 1000(以8个比特位作为例子说明)
12的二进制表达为:0000 1100
8^12就等同于0000 1000 ^0000 1100
结果为:0000 0100
观察标黄的三个二进制序列,我们不难发现,异或结果为1的位置,对应在两个数据处比特位恰好相反。

也就是说,我们对于数组中所有元素做异或操作之后得到的数据的二进制序列中值为1的位置就是对应到做异或操作的两个数相应位置的比特位值相异

PS:这里是解决该题的一大关键点,务必理解到位后往下看!

到此,我们就有更进一步的解题思路了。既然这样,我们就可以按照上述特点以异或结果中任意一个比特位为1的位置作为参照标准,对整个数组进行划分,这样就将求两个出现一次的数据问题变成较为简单的球一个数的问题,按照前面引入例子的方法进行操作就好了!

有同学就又有疑问啦。在划分过程中原数组中出现两次的数据会不会被划分到不同的组中去做异或操作呢??==当然不会!!==相同数据的对应比特位一定相同,那么按照我们规定的标准划分时他们肯定会在同一组中。

看到这里,我们的分析过程已经基本搞定!!接下来废话不说,直接上代码:

代码展示

#include <stdio.h>
#include <windows.h>
/*
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。
找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
*/void FindTwoDiffers(int *arr,int len,int *retArr)
{int sum = 0;for (int i = 0; i < len; i++){sum ^= arr[i];}int j = 0;while (j<32){if (sum&(1 << j))break;elsej++;}int num1 = 0;int num2 = 0;for (int k = 0; k < len; k++){if ((arr[k] & (1 << j))==0)//注意运算符优先级问题{num1 ^= arr[k];}else{num2 ^= arr[k];	}}retArr[0] = num1;retArr[1] = num2;
}int main()
{int arr[] = { 3, -3, 5, 7, 8, 2, 10, 3, 5, 7, 8, 2 };int len = sizeof(arr) / sizeof(arr[0]);int retArr[2] = {0};FindTwoDiffers(arr, len,retArr);for (int i = 0; i < 2; i++){printf("%d ",retArr[i]);}system("pause");return 0;
}

在这里插入图片描述
以上就是对这道题目的详细解答,路过的各位看官留下你们足迹~~

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



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

相关文章

哈希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

leetcode-23Merge k Sorted Lists

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

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划