This is the 12th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Topic describes

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once. Note: Your algorithm should have linear time complexity. Can you do it without using extra space? The sample1: Input: [2.2.1] output:1The sample2: Input: [4.1.2.1.2] output:4Through the number of times532.440Submit the number740.226Source: LeetCode//leetcode-cn.com/problems/single-numberCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. Cycle of violence

Return the value of the outer loop without finding the same number

public int singleNumber(int[] nums) {
    outer: for (int i = 0; i < nums.length; i++) {
        if (i == nums.length - 1) {
            return nums[i];
        }
        for (int j = 0; j < nums.length; j++) {
            if (j == i) {
                continue;
            }
            if (nums[i] == nums[j]) {
                continueouter; }}return nums[i];
    }
    return 0;
}
Copy the code

But you don’t have to think about it, the time is order n^2.

2. A hash

They say you can’t create extra space, but it’s always a good idea to try.

Create a hashMap, place the number of occurrences as a key in the map and the number of occurrences as a value in the map. Iterate over the map’s key and return a key with value 1.

public int singleNumber2(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : nums) {
        map.put(i, map.getOrDefault(i, 0) + 1);
    }
    for (Integer s : map.keySet()) {
        if (map.get(s) == 1) {
            returns; }}return 0;
}
Copy the code

3. Bit operations

Magic solution, first a bit of operation just have this problem!

First, let’s review the lower bit operations

In binary

  • The same digits are 0; the different digits are 1
  • 0 to the 0 is 0
  • 0 to the 1 is 1
  • 1 to the 1 is 0

In decimal

  • Any numeric operation with zero bits is equal to itself
  • Any number with its own bit operation is equal to 0

In this problem, there are an odd number of digits. If you remove one of the digits that occurs only once, you do xor with the other digits and the result is 0. Then you do bit operation with the digits that occur only once and the result is the number that occurs only once. The code is also very concise:

public int singleNumber3(int[] nums) {
    int num = 0;
    for (int i : nums) {
        num ^= i;
    }
    return num;
}
Copy the code