Codility OddOccurrencesInArray 问题 - 递归和 Python

Question

我正在尝试使用递归来解决 Codility 中的 OddOccurrencesInArray 问题，其中

• 给定一个包含 N 个元素的数组，N 始终为奇数
• 数组中除一个元素外的所有元素的出现总次数为偶数
• 我们需要编写返回一个不成对值的代码

例如，如果给定的数组是 [9, 3, 9, 3, 7, 9, 9]，则代码必须返回 7，因为这是数组中唯一未配对的元素。

我的解决方案伪代码/思考过程是：

• 对数组进行排序
• 如果前两个元素彼此相等，则删除它们并在数组减去前两个元素（排序后）上再次递归运行求解算法，即如果未找到不成对的元素，我们将继续减小数组的大小
• 如果前两个元素不相等，则数组的第一个元素必须是不成对的项

我的实现是：

def solution(A):
    # write your code in Python 3.6
    if len(A) > 1: 
        A = sorted(A)
        if A[0] != A[1]:
            return A[0]
        else:
            solution(A[2:])
    else:
        return A[0]

我不断收到错误消息

结果类型无效，应为 int，发现 <class 'NoneType'>。运行时错误（测试程序以退出代码 1 终止）

谁能帮我弄清楚这意味着什么以及如何纠正它？从算法上讲，我认为我的解决方案是合理的，并且我不明白为什么它没有返回我指定的整数值。

Answer 1

另一个Python解决方案100%

还有另一种解决方案，我们可以使用异或逻辑。

首先我们一起来回忆一下XOR是什么意思：

我们可以认识到，如果输入 A和输入 B具有相同的位，则 XOR 输出将为零。

另外，如果我们将任何数字与零进行位异或，则肯定会得到相同的数字，因为该数字的位将产生相同的位，这意味着相同的数字。

现在，为了解决异或逻辑的问题，我们首先定义一个数字来保存每次异或输出的结果，所以首先，我们从零开始，我之前说过零与任何数字都会给出相同的数字。

但如果下次我们得到不同的数字，异或结果将是某个未知的数字。

最后肯定会返回未配对的号码。

由于这样的解决方案只需一个循环就可以实现，因此我们需要循环遍历所有元素，如果我们确实在某个时刻中断，则 XOR 的结果将是我们不需要的某个数字！

因此，我们需要确保循环遍历整个数组一次，然后再循环，因为相同数字的位异或将返回零。因此，我们保留在最后的数字是不与任何东西配对的。

检测时间复杂度： O(N) 或 O(N*log(N))

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

Answer 2

我建议采用完全不同的方法。递归方法并不是不正确，但是重复调用sorted效率非常低，尤其是在输入非常大的情况下。

def solve(t):
  s = set()
  for v in t:
    s.add(v) if v not in s else s.remove(v)
  return list(s)

input = [9, 3, 9, 3, 7, 9, 9]
solve(input)

我们可以想象s评估的过程——

{}     # <- initial s
{9}    # <- 9 is added
{9,3}  # <- 3 is added
{3}    # <- 9 is removed
{}     # <- 3 is removed
{7}    # <- 7 is added
{7,9}  # <- 9 is added
{7}    # <- 9 is removed

最后list(s)返回转换{7}为[7]. 为了输出答案，我们可以写一个简单的if/elif/else-

unpaired = solve(input)

if (len(unpaired) < 1):
  print("there are no unpaired elements")
elif (len(unpaired) > 1):
  print("there is more than one unpaired element")
else:
  print("answer:", unpaired[0])

另一种选择是返回solve第一个未配对的元素或None-

def solve(t):
  s = set()
  for v in t:
    s.add(v) if v not in s else s.remove(v)
  for v in s:
    return v          # <- immediately return first element

answer = solve(input)

if answer is None:
  print("no solution")
else:
  print("the solution is", answer)