【Day 71 】2023-01-10 - 260. 只出现一次的数字 III

[azl397985856]

260. 只出现一次的数字 III

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/single-number-iii/

前置知识

• 位运算
• 数组
• 哈希表

  题目描述

  
  给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5] 输出: [3,5] 注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

[bwspsu]

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = a = b = 0
        right_bit = 1
        length = len(nums)
        for i in nums:
            xor ^= i
        while right_bit & xor == 0:
            right_bit <<= 1
        for i in nums:
            if right_bit & i:
                a ^= i
            else:
                b ^= i
        return [a, b]

[FlipN9]

/**
    当两个数字的异或某位值为1时，必然存在两个数字在此位上的值不相同, 
    取最低有效位只是一种划分
    可以通过获取最低有效位把两个数分开
*/
class Solution {
    public int[] singleNumber(int[] nums) {
        int xorsum = 0;
        for (int x : nums)
            xorsum ^= x;
        // 负数如果取相反数，会产生溢出，所以不能用 a & (-a) 取最低有效位
        // INT MIN 第一位是1，其余位是0，所以它的最低有效位就是自己
        int lsb = (xorsum == Integer.MIN_VALUE? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int x : nums) {
            if ((x & lsb) != 0)
                type1 ^= x;
            else
                type2 ^= x;
        }
        return new int[] {type1, type2};
    }
}

[snmyj]

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        int cnt=0;
        if(n==2){
            if(nums[0]!=nums[1]) return nums;
        }
        if(nums[0]!=nums[1]){ 
            cnt++;
            res.push_back(nums[0]);
            }

        for(int i=0,j=1,k=2;k<nums.size();){
           if(nums[i]!=nums[j]&&nums[j]!=nums[k]) {
               cnt++;
               res.push_back(nums[j]);
               if(k==n-1) {
                   res.push_back(nums[k]);
                   return res;
                }
               i=i+1;
               j=j+1;
               k=k+1;

               if(cnt==2) return res;
               continue;
           }
           if(k==n-1&&nums[k]!=nums[j]) {
               res.push_back(nums[k]);
               return res;
               }
           else {
               i++;
               j++;
               k++;
           }
        }
        return res;
    }
};

[chenming-cao]

解题思路

位运算。运用到异或运算的性质: A ^ A = 0, 0 ^ A = A。因为题目中说数组中只有两个只出现一次的数字，先进行全数组异或运算，算出这两个只出现一次的数字的异或结果。之后对数组进行分组希望将这两个数字分到不同的组里。因为1 ^ 0 = 1，我们从低位开始往高位找异或运算结果中第一个出现1的数位，按照此数位进行分组，两个数字一定不在一组，其余数字在各组中一定成对出现，再次进行组内元素异或运算即可求得结果。

代码

class Solution {
    public int[] singleNumber(int[] nums) {
        int[] res = new int[2];
        int xor = 0;
        // perform xor for all the nums, xor = unique1 ^ unique2
        for (int num : nums) {
            xor ^= num;
        }
        // find the first different digit between unique1 and unique2
        // starting from least significant digit
        int mask = 1;
        while ((xor & mask) == 0) {
            mask = mask << 1;
        }
        // divide the nums into two groups, one has 0 at the corresponding digit
        // and one has 1 at the corresponding digit
        // unique1 and unique2 must be in two different groups
        for (int num : nums) {
            if ((num & mask) == 0) {
                res[0] ^= num;
            }
            else {
                res[1] ^= num;
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为数组长度
• 空间复杂度：O(1)

[bookyue]

code

    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) xor ^= num;

        int num1 = 0;
        int lowbit = xor & (-xor);
        for (int num : nums) {
            if ((num & lowbit) == 0) num1 ^= num;
        }

        return new int[] {xor ^ num1, num1};
    }

[tiandao043]

思路

异或，第一遍异或得到两个出现一次的值的异或结果。 然后找从后往前第一个1作为过滤，说明这位两个值不同。 第二遍将这位1和0分成两组，分别异或，得到这两组里各自只出现一遍的。

代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int res=0;
        for(int n:nums){
            res^=n;
        }
        int div=1;
        while((div&res)==0){
            div<<=1;
        }
        int a=0,b=0;
        for(auto& n:nums){
            if(div & n){
                a^=n;
            }
            else{
                b^=n;
            }
        }
        return vector<int>{a,b};
    }
};

O(n) O(1)

[zywang0]

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorsum = 0;
        for (int x : nums)
            xorsum ^= x;
        int lsb = (xorsum == Integer.MIN_VALUE? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int x : nums) {
            if ((x & lsb) != 0)
                type1 ^= x;
            else
                type2 ^= x;
        }
        return new int[] {type1, type2};
    }
}

[JancerWu]

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) xor ^= num;
        int pos = -1;
        for (int i = 0; i < 32 && pos == -1; i++) {
            if (((1 << i) & xor) != 0) pos = i;
        }
        int[] ans = new int[2];
        for (int num : nums) {
            if (((1 << pos) & num) != 0) ans[0] ^= num;
            else ans[1] ^= num;
        }
        return ans;
    }
}

[mayloveless]

思路

异或一次，求两数之异或。结果sum再和负sum取与，求出差异点，然后所有数通过和这个差异点与运算，相同的数字会变成1，结果会是与差异点相同和不同的两个数。

代码

var singleNumber = function(nums) {
    let xorsum = 0;

    for (const num of nums) {
        xorsum ^= num;
    }
    let type1 = 0, type2 = 0;
    // 取出 xorsum 的二进制表示中最低位那个 1
    // 说明该位上，一个数是1，另一个是0
    const lsb = xorsum & (-xorsum);
    for (const num of nums) {
        if (num & lsb) {// 是1的一起异或，最后剩下是1的数
            type1 ^= num;
        } else {
            type2 ^= num;
        }
    }
    return [type1, type2];
};

复杂度

时间：O(n) 空间O（1）

[A-pricity]

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function(nums) {
    nums.sort();
    const stack = [nums[0]];
    let i = 1;
    while(i < nums.length) {
        const cur = stack[stack.length - 1];
        if(cur === nums[i]) {
            stack.pop();
        } else {
            stack.push(nums[i]);
        }
        i++;
    }
    return stack;
};

[Jetery]

[260. 只出现一次的数字 III]()

思路

• 原理:
  1. a ^ a = 0
  2. a ^ 0 = a

假设数组中仅出现一次的数字为 x, y 那么将数组全部异或之后, 得到 x_or = x ^ y, 找到 x_or 的二进制中第一次出现 1 的下标 f, f 可划分 x 和 y 接下来再次遍历数组, 按照当前数字num & f分为两类, 两类中的数字全部异或即可分别得到 x 和 y

代码 (cpp)

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> ans(2, 0);
        int x_or = 0;
        for (int num : nums) x_or ^= num;

        int f = 1;
        while ((f & x_or) == 0) f <<= 1;

        for (int num : nums) {
            if (num & f) ans[0] ^= num;
            else ans[1] ^= num;
        }
        return ans;
    }
};

复杂度分析

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

[BruceZhang-utf-8]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int[] singleNumber(int[] nums) {
    int diff = 0;
    for (int n : nums) {
        diff ^= n;
    }
    diff = Integer.highestOneBit(diff);
    int[] result = { 0, 0 };
    for (int n : nums) {
        if ((diff & n) == 0) {
            result[0] ^= n;
        } else {
            result[1] ^= n;
        }
    }
    return result;
    }
}

[paopaohua]

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorsum = 0;
        for (int num : nums) {
            xorsum ^= num;
        }
        // 防止溢出
        int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int num : nums) {
            if ((num & lsb) != 0) {
                type1 ^= num;
            } else {
                type2 ^= num;
            }
        }
        return new int[]{type1, type2};
    }
}

• 时间复杂度o(n) n为数组长度
• 空间复杂度o(1)

[RestlessBreeze]

code

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int num: nums) {
            ++freq[num];
        }
        vector<int> ans;
        for (const auto& [num, occ]: freq) {
            if (occ == 1) {
                ans.push_back(num);
            }
        }
        return ans;
    }
};

[klspta]

class Solution {
    public int[] singleNumber(int[] nums) {
        int x = 0;
        for (int num : nums) {
            x ^= num;
        }
        // 防止溢出
        int a = (x == Integer.MIN_VALUE ? x : x & (-x));
        int t1 = 0;
        int t2 = 0;
        for (int num : nums) {
            if ((num & a) != 0) {
                t1 ^= num;
            } else {
                t2 ^= num;
            }
        }
        return new int[]{t1, t2};
    }
}

[yuexi001]

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorsum = 0;
        for (int num: nums) {
            xorsum ^= num;
        }

        int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int num: nums) {
            if (num & lsb) {
                type1 ^= num;
            }
            else {
                type2 ^= num;
            }
        }
        return {type1, type2};
    }
};

[saitoChen]

思路

使用Map计算次数，最后遍历

代码

var singleNumber = function(nums) {
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    const ans = [];
    for (const [num, occ] of freq.entries()) {
        if (occ === 1) {
            ans.push(num);
        }
    }
    return ans;
};

复杂度分析

时间复杂度： O(N) 空间复杂度：O(N)

[Elsa-zhang]

# 260. 只出现一次的数字 III
from collections import Counter

class Solution:
    def singleNumber(self, nums: list[int]) -> list[int]:
        # count = Counter(nums)
        # ans = [k for k,v in count.items() if v==1]
        # return ans

        xorsum = 0
        for num in nums:
            xorsum ^= num

        # lsb = xorsum & (-xorsum)
        lsb = 1
        while lsb & xorsum == 0:
            lsb <<= 1
        type1 = type2 = 0
        for num in nums:
            if num & lsb:
                type1 ^= num
            else:
                type2 ^= num

        return [type1, type2]

nums = [1,2,1,3,2,5] 
s = Solution()
ans = s.singleNumber(nums)
print(ans)

[whoam-challenge]

def singleNumber(self, nums: List[int]) -> List[int]:
    freq = Counter(nums)
    return [num for num, occ in freq.items() if occ == 1]

[buer1121]

class Solution: def singleNumber(self, nums: List[int]) -> List[int]:

位运算

    xor = a = b = 0
    right_bit = 1
    length = len(nums)
    for i in nums:
        xor ^= i
    while right_bit & xor == 0:
        right_bit <<= 1
    for i in nums:
        if right_bit & i:
            a ^= i
        else:
            b ^= i
    return [a, b]

[Ryanbaiyansong]

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # 2 个 elments 出现 1次
        # 所有的别的elements 出现2次
        xor_res = 0
        for x in nums:
            xor_res ^= x 
        low_bit = xor_res & (-xor_res)
        type1 = type2 = 0
        for x in nums:
            if low_bit & x:
                type1 ^= x 
            else:
                type2 ^= x 
        return [type1, type2]