剑指offer | 面试题40：数组中数字出现的次数

千羽

发布于 2022-02-23 15:36:51

4870

发布于 2022-02-23 15:36:51

文章被收录于专栏：程序员千羽程序员千羽

死磕算法系列文章

“Leetcode :

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_40_singleNumbers_2/Solution.java

剑指 Offer 56 - I. 数组中数字出现的次数

“题目描述 ：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 难度：中等

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

方法一：异或

异或运算有个重要的性质，两个相同数字异或为 0。因此，若将 nums 中所有数字执行异或运算，留下的结果则为 出现一次的数字 x ，即：

设 nums = [3, 3, 4, 4, 1]，以上计算流程如下图所示。

算法流程:

遍历nums执行异或:

设整型数组nums= [a, a,b,.,..,x,y,对nums中所有数字执行异或，得到的结果为x⊕y

循环左移计算m :

根据异或运算定义，若整数xy某二进制位为1，则x和y的此二进制位一定不同。换言之，找到 x⊕y勒1的二进制位，即可将数组nums拆分为上述的两个子数组。根据与运算特点，可知对于任意整数a有:
- 若a&0001=1,则a的第一位为1 ;
- 若a&0010= 1，则a的第二位为1 ;
- 以此类推
因此，初始化一个辅助变量m= 1，通过与运算从右向左循环判断，可获取整数x⊕y首位1,记录于m中，代码如下:

拆分nums为两个子数组:
分别遍历两个子数组执行异或:

通过遍历判断nums中格数字和m做与运算的结果，可将数组拆分为两个子数组,分别对两个子数组遍历求异或，则可得到两个只出现一次的数字，代码如下:

返回值:

返回只出现一次的数字 X, Y 即呵。

复杂度分析:

时间复杂度O (N) ：线性遍历nums使用O(N)时间，遍历x田y二进制位使用0(32)= 0(1)时间。
空间复杂度O (1) ：辅助量a,b,x ,y使用常数大小额外空间。

package com.nateshao.sword_offer.topic_40_singleNumbers;

/**
 * @date Created by 邵桐杰 on 2022/1/18 21:33
 * @微信公众号 千羽的编程时光
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 1, 4, 6};
        System.out.println("singleNumbers(arr) = " + singleNumbers(arr));
    }

    public static int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for (int num : nums)               // 1. 遍历异或
            n ^= num;
        while ((n & m) == 0)               // 2. 循环左移，计算 m
            m <<= 1;
        for (int num : nums) {              // 3. 遍历 nums 分组
            if ((num & m) != 0) x ^= num;  // 4. 当 num & m != 0
            else y ^= num;                // 4. 当 num & m == 0
        }
        return new int[]{x, y};          // 5. 返回出现一次的数字
    }
    
}

剑指 Offer 56 - II. 数组中数字出现的次数

“题目描述 ：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 难度：中等

示例 1：

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

示例 2：

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

方法：HashMap

使用HashMap的原理是统计每个数字出现的次数，因为只有一个数字出现一次，其他都出现3次，我们只需要返回那个出现一次的即可，原理比较简单，我们来看下代码

package com.nateshao.sword_offer.topic_40_singleNumbers_2;

import java.util.HashMap;
import java.util.Map;

/**
 * @date Created by 邵桐杰 on 2022/1/18 21:33
 * @微信公众号 千羽的编程时光
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = {9, 1, 7, 9, 7, 9, 7};
        int[] arr2 = {3,4,3,3};
        System.out.println("singleNumber(arr) = " + singleNumber(arr));
        System.out.println("singleNumber(arr2) = " + singleNumber(arr2));
    }

    public static int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        //先把数字存储到map中，其中key存储的是当前数字，value是
        //数字的出现的次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //最后在遍历map中的所有元素，返回value值等于1的
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1)
                return entry.getKey();
        }
        return -1;
    }
}

参考链接：

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/shu-ju-jie-gou-he-suan-fa-san-chong-jie-4b9se/

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2022-01-18，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树