LeetCode 1

20171112 发布于2019-08-14 11:44 / 417人阅读

摘要：如果存储空间的话，首先是很容易达到。然后要求就不能排序了，基于比较的排序最低就是了。原链接主要原理是应用异或来处理。复习一下异或相同为，不同为，同或相同为，不同为。

Single Number https://oj.leetcode.com/problems/single-number/

Given an array of integers, every element appears twice except for one. Find that single one.Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

这道题需要的是线性时间并且不需要额外的存储空间，刚开始我以为是不能有自己的中间变量，后来看论坛里讨论的意思是有常量数量的存储空间也可以，即存储空间为O(1)，运行时间为O(n)就行了。

刚开始想了几种复杂度比较高的，首先如果存储空间能为O(n)，运行时间达到O(n)还是很容易的。

如果存储空间O(1)的话，首先nlog(n)是很容易达到。只要对数组做一下快排nlog(n)，然后再扫描一遍，判断每一个数字和后面的数字或前面的数字是否相同，就能找到 Single Number 。

然后要求O(n)就不能排序了，基于比较的排序最低就是nlog(n)了。最后在网上找到了线性的方法。

原链接：http://www.cnblogs.com/changchengxiao/p/3413294.html

主要原理是应用异或来处理。复习一下异或：相同为0，不同为1，同或：相同为1，不同为0。

所以0 xor X = X, X xor X = 0，又由于异或是可交换的，所以将所有的数组元素都异或一下，出现两次的都交换到一起，变成了0，最后剩下的就是 Single Number 。

public class Solution {
    public int singleNumber(int[] A) {

        if (A == null || A.length == 0) return 0;
        int result = A[0];
        for(int i = 1; i < A.length; i++){
            result = result ^ A[i];
        }
        return result;
    }
}

私有云服务器托管 LeetCode LeetCode_String leetcode_35_SearchIn 网络1+1

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

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

6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月汇总（109 题攻略）

摘要：每天会折腾一道及以上题目，并将其解题思路记录成文章，发布到和微信公众号上。三汇总返回目录在月日月日这半个月中，做了汇总了数组知识点。或者拉到本文最下面，添加的微信等会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 评论0 收藏0
[LeetCode] 811. Subdomain Visit Count

Problem A website domain like discuss.leetcode.com consists of various subdomains. At the top level, we have com, at the next level, we have leetcode.com, and at the lowest level, discuss.leetcode.com...

jzman 2019-08-19 11:11 评论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
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0