Python每日一练(20230515) 只出现一次的数字 I\II\III

2023-05-29 130

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Python每日一练(20230515) 只出现一次的数字 I\II\III

leetcode题号： 136, 137, 260

1. 只出现一次的数字 Single Number

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

代码1： 用哈希表计数

def singleNumber(nums):
    hash_map = {}
    for num in nums:
        if num in hash_map:
            hash_map[num] += 1
        else:
            hash_map[num] = 1
    for num, count in hash_map.items():
        if count == 1:
            return num
    return 0
if __name__ == '__main__':
    nums = [2, 2, 1]
    print(singleNumber(nums))
    nums = [4, 1, 2, 1, 2]
    print(singleNumber(nums))

代码2：异或运算

def singleNumber(nums):
    res = 0
    for num in nums:
        res ^= num
    return res
if __name__ == '__main__':
    nums = [2, 2, 1]
    print(singleNumber(nums))
    nums = [4, 1, 2, 1, 2]
    print(singleNumber(nums))

代码3： 算术运算

def singleNumber(nums):
    hash_map = {}
    sum1, sum2 = 0, 0
    for num in nums:
        if num in hash_map:
            hash_map[num] += 1
        else:
            hash_map[num] = 1
        sum1 += num
    for num, count in hash_map.items():
        sum2 += 2 * num
    return sum2 - sum1
if __name__ == '__main__':
    nums = [2, 2, 1]
    print(singleNumber(nums))
    nums = [4, 1, 2, 1, 2]
    print(singleNumber(nums))

输出：

2. 只出现一次的数字 II Single Number II

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。

示例 1：

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

输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]

输出：99

提示：

1 <= nums.length <= 3 * 10^4

-2^31 <= nums[i] <= 2^31 - 1

nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

进阶：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

代码1：用哈希表计数

def singleNumber(nums):
    hash_map = {}
    for num in nums:
        if num in hash_map:
            hash_map[num] += 1
        else:
            hash_map[num] = 1
    for num, count in hash_map.items():
        if count == 1:
            return num
    return 0
if __name__ == '__main__':
    nums = [2, 2, 3, 2]
    print(singleNumber(nums))
    nums = [0, 1, 0, 1, 0, 1, 99]
    print(singleNumber(nums))

代码2： 位运算

def singleNumber(nums):
    res = 0
    for i in range(64):
        sum = 0
        for num in nums:
            sum += (num >> i) & 1
        if sum % 3 != 0:
            res |= 1 << i
    return res
if __name__ == '__main__':
    nums = [2, 2, 3, 2]
    print(singleNumber(nums))
    nums = [0, 1, 0, 1, 0, 1, 99]
    print(singleNumber(nums))

代码3： 算术运算

def singleNumber(nums):
    nums_set = set(nums)
    sum1 = sum(nums)
    sum2 = 3 * sum(nums_set)
    return (sum2 - sum1) // 2
if __name__ == '__main__':
    nums = [2, 2, 3, 2]
    print(singleNumber(nums))
    nums = [0, 1, 0, 1, 0, 1, 99]
    print(singleNumber(nums))

输出：

3. 只出现一次的数字 III Single Number III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：

输入：nums = [1,2,1,3,2,5]

输出：[3,5]

解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]

输出：[-1,0]

示例 3：

输入：nums = [0,1]

输出：[1,0]

提示：

2 <= nums.length <= 3 * 10^4

-2^31 <= nums[i] <= 2^31 - 1

除两个只出现一次的整数外，nums 中的其他数字都出现两次

代码1：用哈希表计数

def singleNumber(nums):
    m, res = {}, []
    for num in nums:
        m[num] = m.get(num, 0) + 1
    for num, count in m.items():
        if count == 1:
            res.append(num)
    return res
if __name__ == '__main__':
    nums = [1, 2, 1, 3, 2, 5]
    print(singleNumber(nums))
    nums = [-1, 0]
    print(singleNumber(nums))
    nums = [0, 1]
    print(singleNumber(nums))

代码2： 位运算分组异或

def singleNumber(nums):
    xor = 0
    for num in nums:
        xor ^= num
    mask = 1
    while (xor & mask) == 0:
        mask <<= 1
    a, b = 0, 0
    for num in nums:
        if num & mask != 0:
            a ^= num
        else:
            b ^= num
    return [a, b]
if __name__ == '__main__':
    nums = [1, 2, 1, 3, 2, 5]
    print(singleNumber(nums))
    nums = [-1, 0]
    print(singleNumber(nums))
    nums = [0, 1]
    print(singleNumber(nums))