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

The number of occurrences of a number in an array

In an array nums, all numbers appear three times except one. Please find the number that appears only once.

Example 1:

Input: nums = [3,4,3,3]

Output: 4

Example 2:

Input: nums = [9,1,7,9,7,9,7]

Output: 1.

Limitations:

1 <= nums.length <= 10000 1 <= nums[i] < 2^31

Answer key

Method 1: Finite state automata – Java

Bit-operation rules are the same for all bits, so only one bit is considered. As shown in the figure below, there are three states for the number of binary 1 in all numbers, that is, the remainder of 3 is 0, 1, 2.

If binary bit 1 is entered, the state transitions in the following order;

If the binary bit 0 is entered, the state remains unchanged.

This is an analysis of the “one bit” of the binary number, but the other 31 bits of int have the same operation rules, so we can apply the above formula directly to the 32 bits.

After iterating through all the numbers, each bit is in state 00 and state 01 (depending on whether the bits of “once-only number” are 1 or 0), and these two states are recorded by one (twOS is always 0 in these two states), so return ONES.

class Solution {
    public int singleNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int cur = 0;
            int div = 1;
            for (int j = 0; j < nums.length; j++) {
                if ((nums[j] & (div << i)) > 0) { cur++; }}if (cur % 3= =1) { res ^= div << i; }}returnres; }}Copy the code

Time complexity O(N) : the length of the n-bit array NUMs; The traversal number group occupies O(N), and the constant bit operation in each round occupies O(1)O(32×3×2)=O(1).

Spatial complexity O(1) : The variables onesones, Twostwos use extra space of constant size.

Method 1: Finite state automata — Go

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            // for each bit of int
            int bit = 0;
            // Compute the sum of the bits
            for (int num : nums) {
                bit += ((num >> i) & 1);
            }
            // Mod 3 is the value of res at that position
            res += ((bit % 3) << i);
        }
        returnres; }}Copy the code