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

剑指offer最优解免费

本问题对应的 leetcode 原文链接：剑指 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]

限制：

2 <= nums.length <= 10000

解题思路

视频讲解直达：本题视频讲解

代码实现

class Solution {
    public int[] singleNumbers(int[] nums) {
        int z = 0;
        for(int i = 0;i < nums.length; i++){
            z = z ^ nums[i];
        }

        int m = 1;
        while((m & z) == 0){
            m = m << 1;
        }

        int x = 0, y = 0;

        for(int i = 0;i < nums.length; i++){
            if((nums[i] & m) == 0){
                //结果为 0 的子数组，一边统计用异或统计x
                x = x ^ nums[i];
            } else {
                //结果为 1 的子数组，一边统计用异或统计y
                y = y ^ nums[i];
            }
        }

        return new int[]{x, y};
    }
}

时间复杂度：O(n)
额外空间复杂度：O(1)

Python

class Solution(object):
    def singleNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        z = 0
        for i in range(len(nums)):
            z = z ^ nums[i]

        m = 1
        while (m & z) == 0:
            m = m << 1

        x, y = 0, 0

        for i in range(len(nums)):
            if (nums[i] & m) == 0:
                # 结果为 0 的子数组，一边统计用异或统计 x
                x = x ^ nums[i]
            else:
                # 结果为 1 的子数组，一边统计用异或统计 y
                y = y ^ nums[i]

        return [x, y]

C++

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int z = 0;
        for(int i = 0; i < nums.size(); i++){
            z = z ^ nums[i];
        }

        int m = 1;
        while((m & z) == 0){
            m = m << 1;
        }

        int x = 0, y = 0;

        for(int i = 0; i < nums.size(); i++){
            if((nums[i] & m) == 0){
                // 结果为 0 的子数组，一边统计用异或统计 x
                x = x ^ nums[i];
            } else {
                // 结果为 1 的子数组，一边统计用异或统计 y
                y = y ^ nums[i];
            }
        }

        return vector<int>{x, y};
    }
};

Go

func singleNumbers(nums []int) []int {
    z := 0
    for i := 0; i < len(nums); i++ {
        z = z ^ nums[i]
    }

    m := 1
    for (m & z) == 0 {
        m = m << 1
    }

    x, y := 0, 0

    for i := 0; i < len(nums); i++ {
        if (nums[i] & m) == 0 {
            // 结果为 0 的子数组，一边统计用异或统计 x
            x = x ^ nums[i]
        } else {
            // 结果为 1 的子数组，一边统计用异或统计 y
            y = y ^ nums[i]
        }
    }

    return []int{x, y}
}

JS

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumbers = function(nums) {
    let z = 0;
    for (let i = 0; i < nums.length; i++) {
        z = z ^ nums[i];
    }

    let m = 1;
    while ((m & z) == 0) {
        m = m << 1;
    }

    let x = 0,
        y = 0;

    for (let i = 0; i < nums.length; i++) {
        if ((nums[i] & m) == 0) {
            //结果为 0 的子数组，一边统计用异或统计x
            x = x ^ nums[i];
        } else {
            //结果为 1 的子数组，一边统计用异或统计y
            y = y ^ nums[i];
        }
    }

    return [x, y];
};

剑指offer题解