LeetCode 260 Single Number III(只出现一次的数字 III)(*)

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50686236 原文给定一个数字数组nums,其中有两个元素只出现一次,而其他所有元素均出现两次。
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50686236

原文

给定一个数字数组nums,其中有两个元素只出现一次,而其他所有元素均出现两次。

找出这两个只出现一次的元素。

例如:

给定nums = [1, 2, 1, 3, 2, 5],返回[3, 5]。

备注:
1, 返回结果的顺序不重要。所以在上例中,返回[3, 5]也是正确的。
2, 你的算法应该运行在线性时间复杂度。你可以只用常量空间复杂度来实现它吗?

原文

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. 

Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
1. The order of the result is not important. So in the above example, [5, 3] is also correct.

2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

分析

本题我曾在《剑指Offer》中见过,记得要用位运算,自己实现了一遍,不过再看了看书上的,并没有书上的规范,所以最后贴了书上的代码……

其实有这么一个性质:

任何数字异或其自身都等于零。

可能有读者不了解什么是异或,那么就来插播一下:

异或,英文为exclusiveOR,或缩写成xor,异或是一个被用于逻辑运算的数学符号。其数学符号是“⊕”,计算机符号是“xor”。

a⊕b=(¬a∧b)∨(a∧¬b)

true ⊕ false -> true
false ⊕ true -> true
true ⊕ true -> false
false ⊕ false -> false

也就是说两个值相同则异或结果为假,两个值不同则异或为真。所以任何数字异或其自身都等于零,因为两个值相同。

好了,切入正题。就以题目中给出的数组为例吧:

[1, 2, 1, 3, 2, 5, 6, 5, 4, 6]

分别换算成二进制如下:
00010010000100110010
01010110010101000110

对所有数组进行异或运算得出的结果是:0111

于是进行分组如下:
A组: 00011)、00102)、00011)、00113)、00102)
B组: 01015)、01106)、01016)、01004)、01105)

对A组进行再次异或运算的结果是:00113)

对B组进行再次异或运算的结果是:01004

判断该数字的二进制第n位是否是1的函数:

bool IsBit1(int num, unsigned int index) {
    num = num >> index;
    return (num & 1);
}`

找出该数字二进制中第一个1的函数:

unsigned int FindFirstBigIs1(int num) {
    int indexBit = 0;
    while (((num & 1) == 0) && (indexBit < 8 * sizeof(int))) {
        num = num >> 1;
        ++indexBit;
    }
    return indexBit;
}

根据LeetCode的函数模板修改了一点:

vector<int> singleNumber(vector<int>& nums) {
    vector<int> singleV;
    if (nums.size() <= 0) return singleV;

    int resultExclusiveOR = 0;
    for (int i = 0; i < nums.size(); ++i)
        resultExclusiveOR ^= nums[i];

    unsigned int indexOf1 = FindFirstBigIs1(resultExclusiveOR);

    int singleNum1 =0, singleNum2 = 0;
    for (int j = 0; j < nums.size(); ++j) {
        if (IsBit1(nums[j], indexOf1))
            singleNum1 ^= nums[j];
        else
            singleNum2 ^= nums[j];    
    }

    singleV.push_back(singleNum1);
    singleV.push_back(singleNum2);
    return singleV;
}

还有两道相关的题:

LeetCode 136 Single Number(只出现一次的数字)
LeetCode 137 Single Number II(只出现一次的数字 II)(*)

目录
相关文章
|
6月前
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
66 1
|
6天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
6 0
|
6月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
22 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
|
存储 前端开发 算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
112 0
|
算法 PHP
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
110 0
|
算法 PHP
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
106 0
|
算法 PHP
力扣(LeetCode)算法题解:1295. 统计位数为偶数的数字
力扣(LeetCode)算法题解:1295. 统计位数为偶数的数字
88 0
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number

热门文章

最新文章