The title

LeetCode 136. Type of numeric association that occurs only once: bit-operated hash tables

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? Example 1: input: [2, 2, 1] output: 1 example 2: input:,1,2,1,2 [4] output: 4Copy the code

Time to solve the problem.

class Solution {
    public int singleNumber(int[] nums) {
        
        
        
    }
}

Copy the code

The method input parameters are given above to complete the answer.

Subject analysis

  1. There are several ways to solve the problem
  2. The first is to use collections to store numbers. Each number in the set is iterated, if it is not in the set, it is added to the set, if it is already in the set, it is deleted from the set, and the last remaining number is the number that appears only once.
  3. Second, a hash table is used to store each number and the number of occurrences of that number. Iterate through the number group to get the number of occurrences of each number, and update the hash table, and finally iterate through the hash table to get the number that occurs only once.
  4. Third, sort the array and then loop through the array to compare values that appear only once
  5. The fourth, officially recommended solution, uses bit arithmetic

The result of the xOR operation on all elements of the array is the number that occurs only once in the array

Answers to analysis

This article provides two solution code, one is to sort first in the search, one is to use the bit operation

Method 1: sort first, search solution success: execution time :7 ms, beat 29.74% Java users memory consumption :38.6 MB, beat 66.68% Java users

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

This article only analysis I do the idea, only for reference, to understand a solution to the idea, other kinds of ideas to do the problem please access the Internet.

Method 2: use bit operation, xOR operation solution success: execution time :1 ms, beat 100.00% Java users memory consumption :38.5 MB, beat 78.23% Java users

class Solution { public int singleNumber(int[] nums) { int single = 0; for (int num : nums) { single ^= num; } return single; }}Copy the code