首页 > 其他分享 >剑指 Offer 56 - I. 数组中数字出现的次数

剑指 Offer 56 - I. 数组中数字出现的次数

时间:2023-05-24 15:46:50浏览次数:58  
标签:数字 nums Offer int 56 异或 num 数组

题目描述:

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。

要求时间复杂度是O(n),空间复杂度是O(1)。

 

 

设 nums=[3,3,4,4,1] ,以上计算流程如下图所示。

 

本题难点: 数组 nums 有 两个 只出现一次的数字,因此无法通过异或直接得到这两个数字。

 

 

while(z & m == 0) // m 循环左移一位,直到 z & m != 0
    m <<= 1

 

for(int num: nums) {
    if((num & m) != 0) x ^= num;  // 若 num & m != 0 , 划分至子数组 1 ,执行遍历异或
    else y ^= num;                // 若 num & m == 0 , 划分至子数组 2 ,执行遍历异或
}
return new int[] {x, y};          // 遍历异或完毕,返回只出现一次的数字 x 和 y

 

 

 

class Solution{
    public int [] singleNumbers(int nums[]){
        int x=0,y=0,n=0,m=1;
        for(int num:nums){// 1. 遍历异或
            n^=num;
        }
        while((n&m)==0){// 2. 循环左移,计算 m
            m<<=1;
        }
        for(int num:nums){// 3. 遍历 nums 分组
        if((num&m)!=0) x^=num;// 4. 当 num & m != 0
            else y^=num;// 4. 当 num & m == 0
        }
        return new int[]{x,y};// 5. 返回出现一次的数字
    }
}

注:

1、&(按位与)运算操作符,在计算机底层计算的原理中,相同位置的二进制序列进行对比,只要有0就是0,两个都是1才是1。

2、|(按位或)运算操作符,在计算机底层计算的原理中,相同位置的二进制序列进行对比,只要有1就是1,两个都是0才是0。

3、^(按位异或)运算操作符,在计算机底层计算的原理中,相同位置的二进制序列进行对比,相同为0,相异为1。

4.^=:两个二进制的对应位相同,结果为0,否则结果为1。a^=b 等效于 a=a^b 按位异或并赋值。

标签:数字,nums,Offer,int,56,异或,num,数组
From: https://www.cnblogs.com/zhz123567/p/17428499.html

相关文章

  • 剑指 Offer II 018(Java). 有效的回文(简单)
    题目:给定一个字符串s,验证s 是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写。本题中,将空字符串定义为有效的 回文串 。 示例1:输入:s="Aman,aplan,acanal:Panama"输出:true解释:"amanaplanacanalpanama"是回文串示例2:输入:s="raceacar"......
  • 【剑指offer】-栈的压入、弹出序列-20/67
    1.题目描述输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的......
  • 【剑指offer】-把二叉树打印成多行-43/67
    1.题目描述从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。2.题目分析非常经典的一道二叉树的题目,做这道题之前需要掌握二叉树的思想和BFS(广度优先搜索、队列思想)我们可以回顾一下最基本的层次遍历,我们是用一个队列来进行存储初始root结点,然后依次放入root的......
  • 【剑指offer】- 求1+2+3+...+n -47/67
    1.题目描述求1+2+3+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。2.题目分析对于这种求1+2+3+…+n的题,我们可以采取3中方法第一种:直接利用等差数列的思想来进行求和return(1+n)*n/2;第二种:利用迭代的思想进行求和intres=......
  • 【剑指offer】- 数组中重复的数字 -48/67
    1.题目描述在一个长度为n的数组nums里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。示例1:输入:[2,3,1,0,2,5,3]输出:2或32.题目分析此题考查的是面试者的沟通能力,......
  • 数据转换-整数字节数组
    在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务1参考《GMT0009-2012SM2密码算法使用规范》第6节“数据转换”在utils.h和utils.c中完成整数与8位字节串的转换功能(10'):intInt2ByteArr(unsignedinti,unsignedchar*ba);intByteArr2Int(unsignedchar*......
  • 不同路径 II(数组、动态规划)、同构字符串(哈希表、字符串)、颠倒二进制位(位运算、分
    不同路径II(数组、动态规划)一个机器人位于一个_mxn_网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?网......
  • 数据转换-整数字节数组
    在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务1参考《GMT0009-2012SM2密码算法使用规范》第6节“数据转换”在utils.h和utils.c中完成整数与8位字节串的转换功能(10'):intInt2ByteArr(unsignedinti,unsignedchar*ba);intByteArr2Int(unsignedchar*ba......
  • uniapp 数组添加不重复元素
    if(this.checkTimes.includes(_item.time)){this.checkTimes=this.checkTimes.filter((item)=>{returnitem!=_item.time;});}else{this.ch......
  • 数据转换-位串字节数组
    在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务1参考《GMT0009-2012SM2密码算法使用规范》第6节“数据转换”在附件中的utils.h和utils.c中完成位串与8位字节串的转换功能(10'):intBitstr2ByteArr(unsignedchar*bs,unsignedchar*ba,int*lba);intByteA......