`

Leetcode - Single Number III

 
阅读更多
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:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

[分析]
参考https://leetcode.com/discuss/52351/accepted-java-space-easy-solution-with-detail-explanations,粘贴下作者解析:
引用
Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:
In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit in the XOR result. Find out the bit.
In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the aforementinoed bit unset. Two different numbers we need to find must fall into thte two distrinct groups. XOR numbers in each group, we can find a number in either group.

Complexity:
Time: O (n)
Space: O (1)


http://www.cnblogs.com/daijinqiao/p/3352893.html 这篇博客中作者给出更一般化的扩展:
引用
给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。
思路:使用二进制模拟a进制,累计二进制位1出现的次数,当次数达到a时,对其清零,这样可以得到b mod a次x,c mod a次y的累加。遍历剩余结果(用ones、twos、fours...变量表示)中每一位二进制位1出现的次数,如果次数为b mod a 或者 c mod a,可以说明x和y的当前二进制位不同(一个为0,另一个为1),据此二进制位将原数组分成两组,一组该二进制位为1,另一组该二进制位为0。这样问题变成“除了一个整数出现a1次(a1 = b 或 a1 = c)外所有的整数均出现a次”,使用和上面相同的方式计算就可以得到最终结果,假设模拟a进制计算过程中使用的变量为ones、twos、fours...那么最终结果可以用ones | twos | fours ...表示。

我实现了一个具体的例子,一个数组中有一个数出现了1次,一个数出现了两次,其余数均出现了3次。代码有些长,希望面试中不用写这么繁琐的扩展~O(∩_∩)O

public class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) //记仅出现一次的两数为a和b, for 循环结束,xor=a^b
            xor ^= num;
        xor &= -xor; // set a 和 b 第一个不同的数位为1,其余位为0
        
        int[] ret = {0, 0};
        for (int num : nums) {
            if ((num & xor) == 0)
                ret[0] ^= num;
            else
                ret[1] ^= num;
        }
        return ret;
    }
}


import java.util.ArrayList;

public class OutlierNumbers {

    public static void main(String[] args) {
        OutlierNumbers obj = new OutlierNumbers();
        int[] nums = {1,2,2,3,3,3,4,4,4,5,5,5};
        int[] ret = obj.getOutliers(nums);
    }
    
    // 一个数出现a次,一个数出现b次,其余数均出现c次的一个具体化例子: a = 1, b = 2, c = 3
    public int[] getOutliers(int[] nums) {
        int ones = 0, twos = 0;
        int mask = 0;
        for (int num : nums) {
            twos |= (ones & num);
            ones ^= num;
            mask = ~(ones & twos);
            ones &= mask;
            twos &= mask;
        }
        int xor = ones ^ twos;
        xor &= -xor;
        int[] ret = new int[2];
        ArrayList<Integer> group1 = new ArrayList<Integer>();
        ArrayList<Integer> group2 = new ArrayList<Integer>();
        for (int num : nums) {
            if ((xor & num) == 0)
                group1.add(num);
            else
                group2.add(num);
        }
        int[] array1 = arrayList2Array(group1);
        int[] array2 = arrayList2Array(group2);
        if (array1.length % 3 == 1)
            ret[0] = getOneOutlier(array1, true);
        else
            ret[0] = getOneOutlier(array1, false);
        if (array2.length % 3 == 1)
            ret[1] = getOneOutlier(array2, true);
        else
            ret[1] = getOneOutlier(array2, false);
        System.out.println(ret[0] + " " + ret[1]);
        return ret;
    }
    public int getOneOutlier(int[] nums, boolean outlierOccurOne) {
        if (nums == null) return Integer.MAX_VALUE;
        if (nums.length < 3) return nums[0]; 
        int ones = 0, twos = 0;
        int mask = 0;
        for (int num : nums) {
            twos |= (ones & num);
            ones ^= num;
            mask = ~(ones & twos);
            ones &= mask;
            twos &= mask;
        }
        if (outlierOccurOne)
            return ones;
        else
            return twos;
    }
    
    public int[] arrayList2Array(ArrayList<Integer> list) {
        int[] array = new int[list.size()];
        for (int i = 0; i < list.size(); i++)
            array[i] = list.get(i);
        return array;
    }
}
分享到:
评论

相关推荐

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

    leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ ...Single Number com.leetcode.tree Balanced Binary Tree Maximum Depth of Binary Tree Same Tree

    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的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 ...

    颜色分类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 ...

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-...

    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% - ...

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

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

    leetcode浇花-LCSolutions:我的力扣解决方案

    leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...

    LeetCode最全代码

    260 | [Single Number III](https://leetcode.com/problems/single-number-iii/) | [C++](./C++/single-number-iii.cpp) [Python](./Python/single-number-iii.py) | _O(n)_ | _O(1)_ | Medium || 268| [Missing ...

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

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

    leetcode答案-leetcode:leetcode

    Single Number 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 Maximum Depth of Binary Tree 这?也太简单了吧。。一行代码,一个尾递归搞定啊。。 终于想清楚了,leetcode的AC率应该是:在线编辑、...

    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动态规划

    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和oj-leetCode:尝试一些OJ

    Single Number 52.2% Easy 371 两个整数的和 51.6% Easy 104 二叉树的最大深度 50.1% Easy 325% Add the Easy 389.数字 49.9% 简单 226 反转二叉树 48.9% 简单 283 移动零点 46.9% 简单 404 左叶总和 45.5% 简单 383...

    只出现一次的数字

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

    leetcode2-codinginterview:Naphda编码面试研究

    leetcode 2 Naphda 编码面试研究 免责声明 该部门不隶属于 Slack 的实际管理部门,是衍生自 Slack 频道内部的独立小组。 内容 如何使用 问题清单 帮助更新 如何使用 简单的。 在 fork 这个仓库之后,在它前面发布你...

    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去除数组重复元素-Arithmetic-Swift:一些算法的swift实现

    LeetCode去除数组重复元素 Arithmetic-Swift 一些算法的swift实现 桶排序 冒泡排序 快速排序 ##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground ...Number 石头游戏 292. Nim Gam

    leetcode双人赛-java_leetcode:java打印letcode

    number. 向后遍历数组,直到获得两个数的和是给定的值 You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single...

    leetcode用例构造-30-Days-LeetCodingChallenge:30天LeetCodingChallenge

    leetcode 用例构造30 天 LeetCodingChallenge C++ 最有效的解决方案 注意:在顶部添加以下内容以优化延迟 static int lambda_0 = []() ...singleNumber (vector&lt; int &gt;& nums) { int res = 0 ; fo

Global site tag (gtag.js) - Google Analytics