`
SunnyYoona
  • 浏览: 361747 次
社区版块
存档分类
最新评论

[LeetCode]*137.Single Number II

 
阅读更多

【题目】

Given an array of integers, every element appearsthreetimes except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

【题意】

给定一个整数数组,每个元素出现了三次,除了一个。找出那个出现一次的数字。

注意:

你的算法应该一个线性时间复杂度完成。你能不能无需使用额外的内存来完成它

【思路一】

所有的数用二进制表示,我们把每个数的第i位取和之后再对3取余,那么只会有两个结果 0 或 1 。 如果为0代表只出现一次的那个数第i位也为0,

如果为1表示只出现一次的那个数第i位也为1。因此取余的结果就是那个 “Single Number”。

下面是一个直接用大小为 32的数组来记录所有 位上的和。

【代码一】

/*---------------------------------------
*   日期:2015-04-26
*   作者:SJF0115
*   题目: 137.Single Number II
*   网址:https://leetcode.com/problems/single-number-ii/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int singleNumber(int A[], int n) {
        int count[32] = {0};
        int result = 0;
        for(int i = 0;i < 32;++i){
            for(int j = 0;j < n;++j){
                if ((A[j] >> i) & 1) {
                    ++count[i];
                }//if
            }//for
            result |= ((count[i] % 3) << i);
        }//for
        return result;
    }
};

int main(){
    Solution solution;
    int A[] = {2,3,4,2,5,2,3,3,5,5};
    int result = solution.singleNumber(A,10);
    // 输出
    cout<<result<<endl;
    return 0;
}

【思路二】

这个算法是有改进的空间的,可以使用掩码变量

方法 2:用 ones 记录到当前处理的元素为止,二进制 1 出现“1 次”(mod 3 之后的 1)的有哪些二进制位;

用 twos 记录到当前计算的变量为止,二进制 1 出现“2 次”(mod 3 之后的 2)的有哪些二进制位。

当 ones 和 twos 中的某一位同时为 1 时表示该二进制位上 1 出现了 3 次,此时需要清零。

即用二进制模拟三进制运算。最终 ones 记录的是最终结果。

【代码二】

/*---------------------------------------
*   日期:2015-04-26
*   作者:SJF0115
*   题目: 137.Single Number II
*   网址:https://leetcode.com/problems/single-number-ii/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ones = 0, twos = 0, threes = 0;
        for(int i = 0;i < n;++i){
            // 出现2次
            twos |= (ones & A[i]);
            // 出现1次
            ones ^= A[i];
            // 当ones和twos中的某一位同时为1时表示该二进制位上1出现了3次
            threes = ones & twos;
            // 二进制位上1出现了3次此时ones和twos对应位上清零
            ones &= ~threes;
            twos &= ~threes;
        }//for
        return ones;
    }
};

int main(){
    Solution solution;
    int A[] = {2,3,4,2,5,2,3,3,5,5};
    int result = solution.singleNumber(A,10);
    // 输出
    cout<<result<<endl;
    return 0;
}


分享到:
评论

相关推荐

    颜色分类leetcode-leetcode.etc:OJ、leetcode等解决方案

    颜色分类leetcode leetcode.etc My solutions of the problems in Online judge website, leetcode, lintcode, etc. leetcode: 13 problems solved lintcode: 49 problems solved Title URL Solution Difficulty ...

    LeetCode最全代码

    137 | [Single Number II](https://leetcode.com/problems/single-number-ii/) | [C++](./C++/single-number-ii.cpp) [Python](./Python/single-number-ii.py) | _O(n)_ | _O(1)_ | Medium ||| 190 | [Reverse Bits]...

    leetcode Single Number II - 位运算处理数组中的数 - 代金桥 - 博客园1

    扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出

    leetcode切割分组-leetcode:leetcode

    136_single_number.py # 位操作:异或(xor)操作 x ^ 0 = x; x ^ x = 0 sum 001_two_sum.py # 求list中能加和成指定值的两个位置 015_3_sum**.py # 求list中能加和成0的三个值 数列 004_median_of_two_sorted_arrays....

    leetcode答案-leetcode-java:leetcode的Java代码

    leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a 2D Matrix Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II ...

    LeetCode去除数组重复元素-Arithmetic-Swift:一些算法的swift实现

    LeetCode去除数组重复元素 Arithmetic-Swift 一些算法的swift实现 桶排序 冒泡排序 快速排序 ##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground 做起来还是相当方便的 已完成题目 ----2016.9.30 两...

    LeetCode:LeetCode题解

    LeetCode LeetCode题解 传送门 # 标题 解决方案 困难 笔记 1个 简单的 ... Remove_Duplicates_From_Sorted_Array_II ... Best_Time_To_Buy_And_Sell_StockII ... Single_NumberII Java 中等的 167 Two_Sum_II_Input_

    leetcode添加元素使和等于-LeetcodePractice:力码练习

    leetcode添加元素使和等于 LeetcodePractice 用C++刷Leetcode题 2. Add Two Numbers You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order ...

    Leetcode的ac是什么意思-LeetCodeInJava:leetcode-java

    Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...

    LeetCode2 Add Two Numbers

    The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading ...

    leetcode分类-LeetCode:LeetCode在线裁判C++

    SingleNumber 其他算法 各种SingleNumber变种 LinkListCycle I II 其他变种 编程之美 Preorder Traversal Inorder Traver sal postorder 非递归 不用栈! 字符串常用操作 字符串 各种转换 Pow(x,n) 优化 ...

    LeetCode:LeetCode解决方案

    preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划

    只出现一次的数字

    只出现一次的数字 题目 给定一个非空整数数组,除了某个元素只出现一次之外,其余每个元素均出现两次。找出那个只出现了一次的元素。... def singleNumber(self, nums: List[int]) -&gt; int: a = 0 for i in n

    leetcode和oj-leetCode:尝试一些OJ

    leetcode 和 oj leetcode 尝试一些OJ。 412 Fizz Buzz 57.8% Easy 344 Reverse String 57.3% Easy 292 Nim Game 54.4% Easy 136 Single Number 52.2% Easy 371 两个整数的和 51.6% Easy 104 二叉树的最大深度 50.1% ...

    leetcode添加元素使和等于-LeetCode:力扣唱片

    leetcode添加元素使和等于 LeetCode LeetCode Record 归并快排的区别: 思想不同:归并从局部到整体,快排从整体到局部 稳定性:归并是稳定排序,快排不是稳定排序 运行时间:归并 $\Theta(n)logn$,快排只是平均...

    leetcode蓄水池JAVA-leetcode-with-[removed]:wrapped_gift:用各种解决方案和单元测试来练习Leetcode

    https://leetcode.com/problems/single-number/ level : - easy tags : - recursive - linked list solutions : - reverseList - runtime : 52 ms, beats 99.80% - memory : 35 MB, beats 47.37% - ...

    dna匹配leetcode-leetcode:leetcode刷题

    dna匹配 leetcode leetcode刷题--C++ ...Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int&gt; Fraction to Recurring Decimal map long long 正负号 Repeated DNA S

    leetcode答案-leetcode:leetcode

    leetcode 答案 leetcode 08/18 Unique Paths 应该是简单的数学排列组合问题,提炼一下其实就一句话:有m个黑球,n个白球,有多少种不同的排列方式。 我数学太差,没找到答案,直接上了动态规划。 Unique Paths II ...

    leetcoderuntimeerrorjava-leetcode:面试准备的数据结构和算法

    singleNumber ( self , nums : List [ int ]) -&gt; int : 它是所谓的“类型提示”(或“函数注释”;自 Python 3.0 起可用)。 -&gt; List[int] 意味着函数应该返回一个整数列表。 nums: List[int], target: int 表示 ...

    leetcode双人赛-java_leetcode:java打印letcode

    leetcode双人赛 工程共分为两个文件夹: A.Alogrithm 算法导论视频、书的相关程序,用于学习算法及数据结构的基础知识 B.Item 零基础学算法(戴艳) 的课后习题 C. leetcode的题目解答,按题目顺序进行排序 Given an...

Global site tag (gtag.js) - Google Analytics