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

Topic describes

Given an integer array nums, exactly two elements appear only once, and all the rest appear twice. Find the two elements that appear only once. You can return the answers in any order.

 

Advanced: Your algorithm should have linear time complexity. Can you do this using just constant space complexity?

 

Example 1: Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer. Example 2: input: nums = [-1,0] output: [-1,0] example 3: input: nums = [0,1] output: [1,0] source: LeetCode link: https://leetcode-cn.com/problems/single-number-iii copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • Today’s algorithm problem is an array problem, where exactly two elements appear only once, and all the rest appear twice. Notice that only two elements appear once.
  • We start with the naive solution, which uses a hashMap to walk through and count all the elements. Then iterate over the hashMap once to retrieve the element that appears once, which is the answer.
  • The space complexity required by the advanced solution can be realized by using the bitwise operation method. Xor operation (xOR) two bits are equal to 0 and different to 1.
  • The common rules of xOR operations are as follows:
  1. Return to zero (any number xor with itself, the result is 0) : a xor a = 0
  2. Identity law (any xor operation with 0 still results in the original number) : A xor 0 = a
  3. Commutative law: A xor b = b xor a
  4. Associative: A xor b xor c = a xor (b xor c) = (a xor b) xor c
  • Use the property of xor operations. We first perform xOR on all elements in NUMS to get xor values for two elements that occur only once.
  • Then take any bit k that is 1 in the binary representation of sum. The KTH bit in sum is 1, which means that the KTH binary representation of the two answers is different.
  • Known as the sum of the first k bit is 1, that in the first k bit one of the two Numbers is zero, a is 1, so the elements in the nums can be divided into two groups, one group of the elements inside the first k bit is 0, another group of 1, for each set of element of novelty or respectively, because there are two other element, or the result is 0, So the xOR result of each set is one of the answers. The implementation code is as follows:

Through the code

  • Simple algorithm
class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int[] ans = new int[2];
        int j = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) { ans[j++] = entry.getKey(); }}returnans; }}Copy the code
  • Bitwise operation method
class Solution {
    public int[] singleNumber(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum ^= num;
        }
        int k = -1;
        for (int i = 31; i >= 0 && k == -1; i--) {
            if (((sum >> i) & i) == 1) {
                k = i;
                break; }}int[] ans = new int[2];
        for (int num : nums) {
            if (((num >> k) & 1) = =1) {
                ans[1] ^= num; 
            } else {
                ans[0] ^= num; }}returnans; }}Copy the code

conclusion

  • The naive solution is O(n) in time and O(n) in space.
  • The bitwise solution is O(n) in time and O(1) in space.
  • Adhere to the algorithm of the day, come on!