首页 > 代码库 > 【LeetCode】Single Number
【LeetCode】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?
解答:
常规解法:先对数组进行排序,然后通过按顺序判断每相邻两个数是否相同即可;
public class Solution { public int singleNumber(int[] A) { Arrays.sort(A); for(int i=0;i<=A.length-1;){ //注意数组只有一个的情况 if((i+1)<=A.length-1){ //判断A[i]是否是最后一个 if(A[i]!=A[i+1]) return A[i]; else i+=2; }else{ return A[i]; } } return -1; } }
位运算解法:使用异或运算 这个程序用了个小技巧:一个整数和它本身异或之后得到值是0,0与其他整数异或得到的是这个整数本身.
public int singleNumber(int[] A){ if(A.length==0) return -1; int result=0; for(int i=0;i<A.length;i++){ result^=A[i]; } return result; }
---EOF---
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。