首页 > 编程语言 >关于异或算法找唯一

关于异或算法找唯一

时间:2023-07-28 13:56:17浏览次数:31  
标签:交换律 数字 nums res 算法 唯一 异或 结合律

1. 公式: 

  a⊕b = b⊕a (交换律

  a⊕b⊕c = a⊕(b⊕c) (结合律)

  a⊕0 = a (恒等率)

  a⊕a = 0 

2. 应用场景:

  给出一些数字,这些数字里面只有一个是不重复的, 请问怎么找到他?

  其实,就是用异或的交换律和结合律, 把这些数字n1 n2 ..... nk 异或起来, 会发现 最终结果就是  nj( 那个不重复的数字)⊕ 0 。。。

  

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let res = 0;

    for(let i = 0; i < nums.length; i ++){
        res ^= nums [i];
    }
    return res;
};

   PS: 我之前用的是暴力解法,耗时是上面的8

 

  

标签:交换律,数字,nums,res,算法,唯一,异或,结合律
From: https://www.cnblogs.com/the-one/p/17587386.html

相关文章

  • 高手算法专项训练-期望问题
    高手算法专项训练-期望问题T1猫抓老鼠​ 我们可以设猫在点\(u\)老鼠在\(v\)点时猫抓到老鼠的期望时间为\(f_{u,v}\),设此时猫的目标点为\(next_{u,v}\),而这个\(next_{u,v}\)很显然可以在跑\(n\)便BFS。注意\(f\)的转移顺序显然由\(u,v\)的距离来决定。所以......
  • 【实践篇】推荐算法PaaS化探索与实践
    作者:京东零售崔宁1.背景说明目前,推荐算法部支持了主站、企业业务、全渠道等20+业务线的900+推荐场景,通过梳理大促运营、各垂直业务线推荐场景的共性需求,对现有推荐算法能力进行沉淀和积累,并通过算法PaaS化打造通用化的推荐能力,提升各业务场景推荐赋能效率,高效赋能业务需求。......
  • 代码随想录算法训练营第四十天| 300.最长递增子序列 674. 最长连续递增序列 718.
    300.最长递增子序列要求:可以删减任意个节点,最后保存最大的递增长度难点:410489如何保证全局的视角,看到很前面的节点是否大于当前的节点,而不是仅仅记录状态思路:dp[n],当子序列的末尾为N时,它的最大子序列长度也就意味着,N在它的子序列中是最大的,遍历这个N之前的所有序......
  • SHA1签名算法,JAVA和C#
    java:publicstaticvoidmain(String[]args)throwsNoSuchAlgorithmException{Stringtoken="31a4a1aa-cffc-4aca-9ef6-0497edf7fbed";Stringnonce="Rzem0rlz19e6GZuZuFKyDzaxiS4baaqn8uvxVnntXKS";Stringtimestamp="1646......
  • 2023“钉耙编程”中国大学生算法设计超级联赛(4)Number Table
    题意对于一个\(2\timesn\)的矩阵,若每行每列数均不同且均\(\in[0,2^k)\),同时\(2n\)个数异或和为\(0\)则称该矩阵合法。给定\(n,k\),求总方案数。做法考虑若只有一行,即求\(n\)个不相同的数异或和为\(0\)的方案数:假定前\(n-1\)个数不同且已确定,此时仅需考虑第\(n\)个数是否在前......
  • 代码随想录算法训练营第二天| LeetCode 977.有序数组的平方 ,209.长度最小的子数组 ,59.
    977.有序数组的平方     题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/    文章讲解:https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html    视频讲解: https://www.bili......
  • 在线催稿:当一位高级视频算法工程师接受采访
    讲师专访是每一届LiveVideoStackCon举办前的固有“热身”和传统节目,我们夹带着为大会做宣传的私心(却也并不为过),但更多的是希望帮助大家多熟悉、多了解这些在音视频技术领域摸爬滚打多年的工程师、开发者,像朋友一样真心接触、平等交流。毕竟,技术的分享本就不应该居高临下,他们也曾是......
  • 【阅读笔记】一种暗通道优先的快速自动白平衡算法
    解决问题:自动白平衡算法中存在白色区域检测错误导致白平衡失效的问题,作者提出了一种基于暗通道优先的白平衡算法。算法思想:图像中白色区域或者高饱和度区域的光线透射率较低,根据以上特性利用暗通道法计算图像中白色区域。算法概述:作者使用何凯明提出的基于暗通道优先的方法......
  • 算法学习笔记(24): 狄利克雷卷积和莫比乌斯反演
    狄利克雷卷积和莫比乌斯反演看了《组合数学》,再听了学长讲的……感觉三官被颠覆……目录狄利克雷卷积和莫比乌斯反演狄利克雷卷积特殊的函数函数之间的关系除数函数和幂函数欧拉函数和恒等函数莫比乌斯函数和欧拉函数卷积的逆元莫比乌斯函数与莫比乌斯反演求法数论分块(整除分......
  • 唯一元素的和
    给你一个整数数组 nums 。数组中唯一元素是那些只出现 恰好一次 的元素。请你返回nums 中唯一元素的和 。示例1:输入:nums=[1,2,3,2]输出:4解释:唯一元素为[1,3],和为4。示例2:输入:nums=[1,1,1,1,1]输出:0解释:没有唯一元素,和为0。示例3:输入:nums=[1,2......