leetcode_136 Single Number

2019-11-06 07:52:05

字体：大中小

来源：转载

供稿：网友

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?

数组中除了一个数单身，其余都是成对的。找出单身数？解析：

法1：网友答案 原理： we use bitwise XOR to solve this PRoblem :

first , we have to know the bitwise XOR in java

0 ^ N = N N ^ N = 0 So….. if N is the single number

N1 ^ N1 ^ N2 ^ N2 ^…………..^ Nx ^ Nx ^ N

= (N1^N1) ^ (N2^N2) ^…………..^ (Nx^Nx) ^ N

= 0 ^ 0 ^ ……….^ 0 ^ N

= N

public int singleNumber(int[] nums) { int ans =0; int len = nums.length; for(int i=0;i!=len;i++) ans ^= nums[i]; return ans;}

法2：先排序再查找，用时10ms

public class Solution { public int singleNumber(int[] nums) { Arrays.sort(nums); for(int i=0;i<nums.length/2;i++){ if(nums[2*i]!=nums[2*i+1]) return nums[2*i]; } return nums[nums.length-1]; }}

法3：借助Map进行查找，用时39ms

public class Solution { public int singleNumber(int[] nums) { // Map存放的是 <数值，数值出现次数> Map<Integer, Integer> map = new HashMap<>(); for(int i=0;i<nums.length;i++){ if(map.containsKey(nums[i])) map.put(nums[i], 2); else map.put(nums[i], 1); } for(Integer i:map.keySet()){ if(map.get(i)==1) return i; } return nums[0]; }}

上一篇：练习项目备选清单

下一篇：蓝桥杯剪邮票