LeetCode 1

20171112 發(fā)布于2019-08-14 11:44 / 590人閱讀

摘要：如果存儲空間的話，首先是很容易達到。然后要求就不能排序了，基于比較的排序最低就是了。原鏈接主要原理是應用異或來處理。復習一下異或相同為，不同為，同或相同為，不同為。

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;
    }
}

GPU云服務器云服務器 LeetCode LeetCode_String leetcode_35_SearchIn 網絡1+1

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64079.html

6-9月技術文章匯總

摘要：分布式的管理和當我在談論架構時我在談啥狀態(tài)碼詳解無狀態(tài)協議和請求支持哪些方法分層協議棧有哪些數據結構運用場景說說你常用的命令為什么要有包裝類面向對象的特征是啥是啥有什么好處系統設計工程在線診斷系統設計與實現索引背后的數據結構及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當我在談論RestFul架構時我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環(huán)枚舉三個數字。總結本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數組知識點。或者拉到本文最下面，添加的微信等會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。 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 題。一目錄不折騰的前端，和咸魚有什么區(qū)別...

tain335 2019-08-26 10:28 評論0 收藏0