This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 137 on LeetCode. The number II appears only once.

Tag: hash table, bit operation

Given an array of integers, nums, each element appears exactly three times except for one element. Find and return the element that appears only once.

Example 1:

Input: nums = [2,2,3,2Copy the code

Example 2:

Input: nums = [0,1,0,1,0, 99] Output: 99Copy the code

Tip:

  • 1 <= nums.length <= 3 *
    1 0 4 10^4

  • –
    2 31 2^{31}     <= nums[i] <=
    2 31 2^{31}     – 1

  • In NUMS, every element appears exactly three times except one

Advanced: Your algorithm should have linear time complexity. Can you do it without using extra space?

Hash table

A naive approach is to use a “hash table” to count and then print out the number that counts 111.

The hash table is stored as “value: number of occurrences of a value”.

Code:

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        for (int x : map.keySet()) {
            if (map.get(x) == 1) return x;
        }
        return -1; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Statistics figures

The space complexity of the hash table solution is O(n)O(n)O(n), and the [Advanced] part of the problem says you should do it in constant space.

One of the more obvious ways to do this is to fix the intintint type to 323232 bits.

Use a length of
32 32 An array of
c n t [ ] cnt[] Keep track of how many times each digit of each value occurs
1 1 And then to
c n t [ ] cnt[] Each bit of the array proceeds
m o d mod
3 3 Operation to repiece values that occur only once.

For example 🌰, consider that the binary representations for example [1,1,1,3], 111, and 333 are 00.. 001 and 00.. 011, CNT [] CNT [] CNT [] CNT [] CNT [] array to get [0,0,… 0,1,4]. Modmodmod 333 yields [0,0,… 0,1,1], which is converted to a decimal number to produce the “once only” answer 333.

Code:

class Solution {
    public int singleNumber(int[] nums) {
        int[] cnt = new int[32];
        for (int x : nums) {
            for (int i = 0; i < 32; i++) {
                if (((x >> i) & 1) = =1) { cnt[i]++; }}}int ans = 0;
        for (int i = 0; i < 32; i++) {
            if ((cnt[i] % 3 & 1) = =1) {
                ans += (1<< i); }}returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

DFA

If we consider the case where every element appears twice except for one, we can use xOR.

Using the property that the same number is different or 0, it can help us to achieve a good state switch:

In this case, each element appears three times except for an element that appears only once, so there are three states of “zero occurrence”, “one occurrence” and “two occurrence”, which means that at least two digits are required to record, and the state conversion relationship is as follows:

So how to express the above DFA in expression? There are several methods:

  1. Use “truth table” to write “logical function expression” can refer to here, the simplification process can refer to the Carnot diagram simplification method.

  2. Memorize the conclusion (this is a classic DFA primer).

  3. Hard to do, bit operation is also that several, not “digital circuit” can not remember the “conclusion”, hit the time to look at the truth table constantly adjust logic can also be written out.

Code:

class Solution {
    public int singleNumber(int[] nums) {
        int one = 0, two = 0;
        for(int x : nums){
            one = one ^ x & ~two;
            two = two ^ x & ~one;
        }
        returnone; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is No.137 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.