leetcode136. Single Number

zhaot 发布于2019-08-15 11:12 / 1486人阅读

摘要：题目要求如何在使用的时间复杂度和的额外空间复杂度来找到一个数组中唯一一个成单的数字。思路一可以通过来记录数字出现的情况。如果已经出现，则将其从中删除。一个数值和另一个数值进行两次异或计算，该数值不变。

题目要求

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

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

如何在使用O(n)的时间复杂度和O(0)的额外空间复杂度来找到一个数组中唯一一个成单的数字。

思路一：hashset

可以通过set来记录数字出现的情况。如果set中不曾出现该数字，则加入set。如果已经出现，则将其从set中删除。最后无法从set中删除的数字，则是single number

    public int singleNumber(int[] nums) {
        Set set = new HashSet();
        for(int i = 0 ; i i = set.iterator() ; i.hasNext() ; ) single = i.next();
        return single;
    }

思路二：排序

如果将array排序后，那么相同的数字一定位于相邻的位置上，只需要比较2k和2k+1位置上的值是否相同就可以了。

    public int singleNumber2(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0 ; i
思路三：bit manipulation
这里就需要提一下异或这个操作符。一个数值和另一个数值进行两次异或计算，该数值不变。也就是说： A XOR B XOR B = A XOR （B XOR B） =  A
在这里也可以试一下具体数值。
其实异或的话，可以用白话来说就是‘要么这个，要么那个’
所以也就是说，如果将array中的所有数值都进行一次异或计算，那么最终的结果也就是那个singleNumber。
    public int singleNumber3(int[] nums) {
        for (int i =1; i < nums.length; i++) {
            nums[i] ^= nums[i-1];
        }
        return nums[nums.length-1];
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云混合云 136企业网盘 single Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67609.html

Leetcode PHP题解--D51 136. Single Number

摘要：题目链接题目分析返回给定数组中，只出现了一次的元素。思路用计算元素出现的次数。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D51 136. Single Number 题目链接 136. Single Number 题目分析返回给定数组中，只出现了一次的元素。思路用array_count_values计算元素出现的次数。再用array_search返回出现次数为1的元素。...

KunMinX 2019-07-01 12:44 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：使用位运算数组只出现一次数字的数组得到最低的有效位，即两个数不同的那一位看完上面的解法，我脑海中只有问号的存在，啥意思啊下面就让我们简单了解一下位运算并解析一下这三道题目。另，负数按补码形式参加按位与运算。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只出现一次以外...

daydream 2019-05-21 11:41 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：简单介绍一下位运算异或运算异或逻辑的关系是当不同时，输出当相同时，输出。另，负数按补码形式参加按位与运算。使一个数的最低位为零，可以表示为。，截止到这儿，三道题目中使用的位运算介绍完毕，那么这里我们插入一下的详细题解。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只...

刘明 2019-05-22 14:21 评论0 收藏0
leetcode部分题目答案之JavaScript版

摘要：自己没事刷的一些的题目，若有更好的解法，希望能够一起探讨项目地址自己没事刷的一些LeetCode的题目，若有更好的解法，希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0