只出现一次的数

水深无声 2021-09-26 15:10 361阅读 0赞

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其他所有元素均出现两次。 找出只出现一次的那两个元素。  
示例:  
给定 nums = \[1, 2, 1, 3, 2, 5\], 返回 \[3, 5\].  
注意：  
结果的顺序并不重要，对于上面的例子 \[5, 3\] 也是正确答案。  
你的算法应该具有线性复杂度，你能否仅使用恒定的空间复杂度来实现它？  
解题思路：  
1.异或运算 因为a^a = 0  
2.将数组分为两组  
3.如3（011）^5（101）=6(110),证明，3和5的倒数第二位不同=> 3&2>0，5&2==0

class Solution { 
        public int[] singleNumber(int[] nums) {
            int[] res = new int[2];//找打两个只出现一次的数
            int temp = 0;
            for (int i = 0; i < nums.length; i++) {
                temp ^= nums[i];
            }
            int tm = (int) Math.pow(2, getLast1(temp));
            res[0] = 0;
            res[1] = 0;
            for (int i = 0; i < nums.length; i++) {
            //分为两组进行异或运算
                 if((nums[i]&tm)>0){
                     res[0] ^= nums[i];
                 }else{
                     res[1] ^= nums[i];
                 }
            }
            return res;
        }
        //找到最后一个1的位置
        public static int getLast1(int n) {
            if(n==0)
                return -1;
            int count = 0;
            while(n!=0){
                if((n&1)==1){
                    return count;
                }else{
                    count++;
                    n = n>>1;
                }
            }
            return count;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，361人围观）

还没有评论，来说两句吧...

相关阅读

相关只出现一次的数算法题汇总

写在前面如果觉得写得好有所帮助，记得点个关注和点个赞，不胜感激! 这篇文章用来总结一个系列的算法题，也就是找到元素数组中重复出现的元素或者只出现一次的元素。其实在讲解

「爱情、让人受尽委屈。」/ 2023年02月10日 03:40/ 0 赞/ 7 阅读

相关只出现一次的数字

> leetcode 136题 \[easy\] > 中：[只出现一次的数字][Link 1] > 英：[Single Number][] > ![在这里插入图片描

以你之姓@/ 2022年12月29日 01:38/ 0 赞/ 145 阅读

相关一组整数中只有一个数只出现一次其余的数都是成对出现的找出这个只出现一次的数

include <stdio.h> include <stdlib.h> int Appearonce(int p,int n); int ma

雨点打透心脏的1/2处/ 2022年12月12日 02:25/ 0 赞/ 142 阅读

相关数组中只出现一次的数

首先看看题目要求：数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法找到x。这个题目非常有意思，在本人博客中有《[位操作基础篇

た入场券/ 2022年08月22日 06:26/ 0 赞/ 181 阅读

相关数组中只出现一次的数

首先看看题目要求：数组A中，除了某一个数字x之外，其他数字都出现了三次，而x出现了一次。请给出最快的方法找到x。这个题目非常有意思，在本人博客中有《[位操作基础篇

超、凢脫俗/ 2022年07月16日 13:17/ 0 赞/ 185 阅读

相关只出现一次的数字

> 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素 > 例：\[1,2,2\] —> 1 方法一

你的名字/ 2022年04月16日 02:09/ 0 赞/ 207 阅读

相关整形数组中查找只出现一次的数

\include<stdio.h> \include<stdlib.h> \define N 5 int main() \{ int sum\[N\],i,j

向右看齐/ 2022年04月05日 06:56/ 0 赞/ 206 阅读

相关 LeetCode136.只出现一次的数

题目： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

水深无声/ 2022年02月18日 12:17/ 0 赞/ 226 阅读

相关只出现一次的数II

给定一个整型数组，除了一个元素只出现一次外，其余每个元素都出现了三次。求出那个只出现一次的数。解体思路：整型数占32位，可以记下所有数每一位的总数，然后每一位对3取

末蓝、/ 2021年09月26日 15:10/ 0 赞/ 302 阅读

相关只出现一次的数

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其他所有元素均出现两次。找出只出现一次的那两个元素。示例: 给定 nums = \[1, 2, 1, 3,

水深无声/ 2021年09月26日 15:10/ 0 赞/ 362 阅读