疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Single Number 数组找出数字


 

        Single Number 数组中找出只出现一次的数字

  题目是这样说的:

  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)就可以了

  于是我一开始这样写也accept了就是利用一个hashmap,记录每个数字出现的个数。

  public class Solution {

  public int singleNumber(int[] A) {

  Map map=new HashMap();

  for(int i=0;i m:map.entrySet()){

  if(m.getValue()==1){

  return m.getKey();

  }

  }

  return 0;

  }

  }

  这个题的标准做法是利用异或运算的这两个法则:

  1. a ^ b = b ^ a

  2. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;

  举个例子:

  1^2^3^4^4^3^2的结果是啥呢?

  一眼大概开不出来

  根据上面两个法则,改变一下顺序吧

  改成2^2^3^3^4^4^1

  现在,结果一目了然了吧~

  显然是1呗。

  有了上面的例子,这道题就简单多了

  public class Solution {

  public int singleNumber(int[] A) {

  int result = A[0];

  for(int i = 1; i < A.length; i++){

  result = result ^ A[i];

  }

  return result;

  }

  }

  完事了。