Codility OddOccurrencesInArray 问题 - 递归和 Python

Question

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

给定一个包含 N 个元素的数组，N 总是奇数
数组中除了一个元素出现的次数都是偶数
我们需要编写代码，使 return 成为一个不成对的值

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

我的解决方案pseudocode/thought过程是：

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

我的实现是：

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，已找到。运行时错误（测试程序以退出代码 1 终止）

任何人都可以帮我弄清楚这是什么意思以及我该如何纠正它？从算法上讲，我认为我的解决方案是合理的，但我不明白为什么它没有return我指定的整数值。

Answer 1

你的递归调用没有 return 任何东西，这意味着你正在 returning None.

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) 是 returned 转换 {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 return 第一个不成对的元素或 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)

Answer 3

另一个Python解决方案100%

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

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

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

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

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

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

最终，没有配对的号码肯定会returned。

因为这样的解决方案只需要一个循环就可以实现，我们需要遍历所有元素，如果我们在某个时候做 break，异或的结果将是一些我们不需要的数字，所以我们需要确保我们遍历整个数组一次，然后因为相同数字的位 XOR 将 return 为零。这样我们就可以在最后保留与任何东西都不成对的数字。

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

def solution(A): 
     
    num = 0; 

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

Answer 4

def solution(A):
    cloned = []
    A.sort()
    if len(A) > 1:
       for itr in A:
          if itr in cloned:
             itrindex = cloned.index(itr)
             cloned.pop(itrindex)
          else:
             cloned.append(itr)
    else:
        return A[0]

    return cloned[0]

Codility OddOccurrencesInArray 问题 - 递归和 Python

Codility OddOccurrencesInArray Problem - Recursion and Python

python

arrays

recursion

nonetype

另一个Python解决方案100%