Go&Java算法之数组中数字出现的次数 数组中数字出现的次

发表于

这是我参与11月更文挑战的第25天，活动详情查看：2021最后一次更文挑战

数组中数字出现的次数

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]

输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]

输出：1

限制：

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

题解

方法一：有限状态自动机——Java

各二进制位的 位运算规则相同 ，因此只需考虑一位即可。如下图所示，对于所有数字中的某二进制位 1 的个数，存在 3 种状态，即对 3 余数为 0, 1, 2 。

若输入二进制位 1 ，则状态按照以下顺序转换；

若输入二进制位 0 ，则状态不变。

以上是对数字的二进制中 “一位” 的分析，而 int 类型的其他 31 位具有相同的运算规则，因此可将以上公式直接套用在 32 位数上。

遍历完所有数字后，各二进制位都处于状态 00 和状态 01 （取决于 “只出现一次的数字” 的各二进制位是 1 还是 0 ），而此两状态是由 one 来记录的（此两状态下 twos 恒为 0 ），因此返回 ones 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Java复制代码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;
            }
        }
        return res;
    }
}

时间复杂度 O(N) ： 其中 N 位数组 nums 的长度；遍历数组占用 O(N) ，每轮中的常数个位运算操作占用 O(1)O(32×3×2)=O(1) 。

空间复杂度 O(1) ： 变量 onesones , twostwos 使用常数大小的额外空间。

方法一：有限状态自动机——Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
go复制代码class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            // 对于int每一位
            int bit = 0;
            // 计算该位上的和
            for (int num : nums) {
                bit += ((num >> i) & 1);
            }
            // 对3取余即为res在该位的值
            res += ((bit % 3) << i);
        }
        return res;
    }
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%