leetcode面试题56 - I. 数组中数字出现的次数

leetcode面试题56 - I. 数组中数字出现的次数

五月 23, 2020

leetcode面试题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]

限制：
2 <= nums <= 10000

基础知识

  • 两个相同数异或为0
  • 异或有交换律
  • 0异或任何数都是任何数本身

    解题思路

    对于数组里面只有一个出现一次的数。只需异或所有数，就是答案。而有两个数的话，异或一遍会是这两个数的异或结果。
    对这两个数的特点分组，分成两个数组，让这两个数在数组里面只出现一次就行了。
    比如最后是2异或6的结果。0010和0110，不用考虑其他的出现两次的数，因为他们的判断条件是一样的，肯定会进同一个数组，现在要区分2和6 。
    2和6的异或结果是0100，异或某一位为1，表示该位两个数是不一样的。此时表示第3位不一样，所以可以根据这个特点来把这两个数分组。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
        public int[] singleNumbers(int[] nums) {
            int xor = 0;
            for (int i = 0; i < nums.length; i++) {
                xor ^= nums[i];
            }
            int div = 1;
            while ((xor & div) == 0) {
            //只需要选取最低位就行了，最低位不一样这两个数就肯定不一样
                div <<= 1;
            }
            int a = 0, b = 0;
            for (int i = 0; i < nums.length; i++) {
            //注意相同的数肯定会走同一个if，所以不用担心相同的数会被分在不同的组
                if ((div & nums[i]) == 0) {
                    a ^= nums[i];
                } else {
                    b ^= nums[i];
                }
            }
            return new int[]{a,b};
        }
    }

leetcode 89/100