首页 > 代码库 > 落单的数

落单的数

<style type="text/css">.title { text-align: center; margin-bottom: .2em } .subtitle { text-align: center; font-size: medium; font-weight: bold; margin-top: 0 } .todo { font-family: monospace; color: red } .done { font-family: monospace; color: green } .priority { font-family: monospace; color: orange } .tag { background-color: #eee; font-family: monospace; padding: 2px; font-size: 80%; font-weight: normal } .timestamp { color: #bebebe } .timestamp-kwd { color: #5f9ea0 } .org-right { margin-left: auto; margin-right: 0px; text-align: right } .org-left { margin-left: 0px; margin-right: auto; text-align: left } .org-center { margin-left: auto; margin-right: auto; text-align: center } .underline { text-decoration: underline } #postamble p,#preamble p { font-size: 90%; margin: .2em } p.verse { margin-left: 3% } pre { border: 1px solid #ccc; padding: 8pt; font-family: monospace; overflow: auto; margin: 1.2em } pre.src { position: relative; overflow: visible; padding-top: 1.2em } pre.src::before { display: none; position: absolute; background-color: white; top: -10px; right: 10px; padding: 3px; border: 1px solid black } pre.src:hover::before { display: inline } pre.src-asymptote::before { content: "Asymptote" } pre.src-awk::before { content: "Awk" } pre.src-C::before { content: "C" } pre.src-clojure::before { content: "Clojure" } pre.src-css::before { content: "CSS" } pre.src-D::before { content: "D" } pre.src-ditaa::before { content: "ditaa" } pre.src-dot::before { content: "Graphviz" } pre.src-calc::before { content: "Emacs Calc" } pre.src-emacs-lisp::before { content: "Emacs Lisp" } pre.src-fortran::before { content: "Fortran" } pre.src-gnuplot::before { content: "gnuplot" } pre.src-haskell::before { content: "Haskell" } pre.src-java::before { content: "Java" } pre.src-js::before { content: "Javascript" } pre.src-latex::before { content: "LaTeX" } pre.src-ledger::before { content: "Ledger" } pre.src-lisp::before { content: "Lisp" } pre.src-lilypond::before { content: "Lilypond" } pre.src-lua::before { content: "Lua" } pre.src-matlab::before { content: "MATLAB" } pre.src-mscgen::before { content: "Mscgen" } pre.src-ocaml::before { content: "Objective Caml" } pre.src-octave::before { content: "Octave" } pre.src-org::before { content: "Org mode" } pre.src-oz::before { content: "OZ" } pre.src-plantuml::before { content: "Plantuml" } pre.src-processing::before { content: "Processing.js" } pre.src-python::before { content: "Python" } pre.src-R::before { content: "R" } pre.src-ruby::before { content: "Ruby" } pre.src-sass::before { content: "Sass" } pre.src-scheme::before { content: "Scheme" } pre.src-screen::before { content: "Gnu Screen" } pre.src-sed::before { content: "Sed" } pre.src-sh::before { content: "shell" } pre.src-sql::before { content: "SQL" } pre.src-sqlite::before { content: "SQLite" } pre.src-forth::before { content: "Forth" } pre.src-io::before { content: "IO" } pre.src-J::before { content: "J" } pre.src-makefile::before { content: "Makefile" } pre.src-maxima::before { content: "Maxima" } pre.src-perl::before { content: "Perl" } pre.src-picolisp::before { content: "Pico Lisp" } pre.src-scala::before { content: "Scala" } pre.src-shell::before { content: "Shell Script" } pre.src-ebnf2ps::before { content: "ebfn2ps" } pre.src-cpp::before { content: "C++" } pre.src-abc::before { content: "ABC" } pre.src-coq::before { content: "Coq" } pre.src-groovy::before { content: "Groovy" } pre.src-bash::before { content: "bash" } pre.src-csh::before { content: "csh" } pre.src-ash::before { content: "ash" } pre.src-dash::before { content: "dash" } pre.src-ksh::before { content: "ksh" } pre.src-mksh::before { content: "mksh" } pre.src-posh::before { content: "posh" } pre.src-ada::before { content: "Ada" } pre.src-asm::before { content: "Assembler" } pre.src-caml::before { content: "Caml" } pre.src-delphi::before { content: "Delphi" } pre.src-html::before { content: "HTML" } pre.src-idl::before { content: "IDL" } pre.src-mercury::before { content: "Mercury" } pre.src-metapost::before { content: "MetaPost" } pre.src-modula-2::before { content: "Modula-2" } pre.src-pascal::before { content: "Pascal" } pre.src-ps::before { content: "PostScript" } pre.src-prolog::before { content: "Prolog" } pre.src-simula::before { content: "Simula" } pre.src-tcl::before { content: "tcl" } pre.src-tex::before { content: "TeX" } pre.src-plain-tex::before { content: "Plain TeX" } pre.src-verilog::before { content: "Verilog" } pre.src-vhdl::before { content: "VHDL" } pre.src-xml::before { content: "XML" } pre.src-nxml::before { content: "XML" } pre.src-conf::before { content: "Configuration File" } table { border-collapse: collapse } caption.t-above { caption-side: top } caption.t-bottom { caption-side: bottom } td,th { vertical-align: top } th.org-right { text-align: center } th.org-left { text-align: center } th.org-center { text-align: center } td.org-right { text-align: right } td.org-left { text-align: left } td.org-center { text-align: center } dt { font-weight: bold } .footpara { display: inline } .footdef { margin-bottom: 1em } .figure { padding: 1em } .figure p { text-align: center } .inlinetask { padding: 10px; border: 2px solid gray; margin: 10px; background: #ffffcc } #org-div-home-and-up { text-align: right; font-size: 70%; white-space: nowrap } textarea { } .linenr { font-size: smaller } .code-highlighted { background-color: #ffff00 } .org-info-js_info-navigation { border-style: none } #org-info-js_console-label { font-size: 10px; font-weight: bold; white-space: nowrap } .org-info-js_search-highlight { background-color: #ffff00; color: #000000; font-weight: bold } .org-svg { width: 90% }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style> <style type="text/css">pre.src { background-color: #002b36; color: #839496 }</style>

落单的数

Table of Contents

  • 1. 题目
  • 2. 挑战
  • 3. 思路

1 题目

给出2*n + 1 个的数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。

2 挑战

循环一次,常数的空间消耗

3 思路

如果没有循环次数限制和常数的空间消耗限制,这个问题很简单。用一个数组来记录数字出现的次数,再找出一次的数字就可以了。

但是用常数的空间消耗,确实没有想到好方法,后来在网上搜到的方法。用亦或来做,真是聪明!

public class Solution {
    /**
      *@param A : an integer array
      *return : a integer 
      */
    public int singleNumber(int[] A) {
        // Write your code here
        int result = 0;
        for(int a: A) {
            result ^= a;
        }
        return result;
    }
}

Date: 2016-12-31 17:00

Created: 2016-12-31 周六 17:21

Validate

落单的数