首页 > 代码库 > Single Number i,ii,iii

Single Number i,ii,iii

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Bit: a ^ a = 0;

public class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int n : nums){
            res ^= n;
        }
        return res;
    }
}

 

137. Single Number II

public class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0 ; i < nums.length ; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            if(entry.getValue() == 1)
                return entry.getKey();
        }
        return 0;
    }
}

 

260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

public class Solution {
    public int[] singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int n: nums){
            if(!set.add(n)){
                set.remove(n);
            }
        }
        Iterator<Integer> it = set.iterator();
        int[] res = new int[2];
        int start = 0;
        while(it.hasNext() && start < res.length){
            res[start] = it.next();
            start++;
        }
        return res;
    }
}

 

二刷可以研究bit做法

Single Number i,ii,iii