时间戳

首页 > 解决方案 > 30 天 LeetCode 四月挑战赛第 1 天 - 单号

python - 30 天 LeetCode 四月挑战赛第 1 天 - 单号

问题描述

我是编码挑战的新手，正在尝试解决 leetCode 上的编码挑战。
任何人都可以帮助我清楚地理解问题以在 python 中编码。不使用额外内存
是什么意思？ 问题 给定一个非空整数数组，除了一个之外，每个元素都出现两次。找到那个单一的。


笔记：

您的算法应该具有线性运行时复杂度。你能在不使用额外内存的情况下实现它吗？

示例 1

Input: [2,2,1]
Output: 1


示例 2

Input: [4,1,2,1,2]
Output: 4

标签： python

解决方案

您可以通过使用运算符来解决此问题，而无需额外的内存XOR。XOR 逻辑运算或异或，采用两个布尔操作数，当且仅当操作数不同时才返回 true。XOR 运算符有 2 个属性：

  • 一个数与自身的异或是0。
  • 数字与 0 的异或是数字本身。

因此，例如，当您执行 2 ^ 2 时，结果将为 0 (0010 ^ 0010 = 0000)，如果您执行 2 ^ 0，则结​​果将为 2 (0010 ^ 0000)。正如问题所说，只有一个数字出现一次，而其他数字出现两次，那么在进行此操作时，相同的数字将相互消除，并给出最终出现一次的数字。

这是 Python 中的简单解决方案，它就地执行（就地意味着您不必创建辅助数据结构来解决问题）：

def find_12_xor(items):
    result = 0
    for item in items:
        result ^= item
    return result

推荐阅读