logo标签列表

Codility奇数次出现问题 - 递归和Python。

pythonarraysrecursionnonetype
4

我正在尝试使用递归来解决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，但发现了。 运行时错误（测试程序以退出代码1终止）

有人能帮我弄清楚这是什么意思以及如何纠正吗？从算法上看，我认为我的解决方案是正确的，但我不明白为什么它没有返回我指定的整数值。

1
递归对于这个问题来说有些过头了；在已排序的数组上循环就足够了。如果你跟踪未配对的值，也可以避免排序。 - Scott Hunter
3
一眼看去，你在代码中忘记了返回solution(A[2:])。 - Jimmy Chen
3
除了对所有数字进行异或运算以外，任何其他方法都是过度设计。 - Kelly Bundy
7个回答
23

另一种Python解决方案100%

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

首先，让我们一起回顾一下什么是异或运算： XOR表

我们可以认识到，如果对于输入A和输入B，它们的位相同，那么异或输出将为零。

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

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

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

最后，肯定会返回没有成对的数字。

由于像这样的解决方案只需要一个循环，我们需要遍历所有元素，如果在某一点上使用了中断（break），则异或运算的结果会是我们不需要的某个数字！

因此，我们需要确保我们只需一次遍历整个数组，然后由于相同数字的位异或运算会返回零，所以最终会得到那个与其他数字没有成对出现的数字。

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

def solution(A): 
     
    num = 0

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

我建议采用完全不同的方法。递归方法并不是错误的，但是如果输入数据非常大，反复调用 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

最终返回转换了{7}为[7]的列表 s。为了输出答案，我们可以编写一个简单的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)
1
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]
1
欢迎来到 Stack Overflow，Stephen。我认为最好在你的答案中加入一些解释，这样其他人就可以理解你解决问题的逻辑！ - Mohamad Ghaith Alzin
1

你的递归调用没有返回任何内容，这意味着你返回了None。

0

使用 PHP 数组函数可以轻松实现这样的功能，它在 Codility 上获得了 100% 的分数。如果 Python 也有类似的数组函数，那么这可能会有所帮助。

function solution($a){
      $result  = array_count_values($a);
     $result = array_filter($result , function($a){
           return ($a  % 2) && 1;
     });
    return key($result);   
}
0

我尝试了多种方法，但性能就是不好！

def solution(A):    
    for i in set(A):
    if A.count(i) == 1:
        return i

这只给了我一个25%的性能得分。不过，我也尝试了其他方法。
from collections import Counter
def solution(A): 
    c = Counter(A)
    final = [k for k, v in c.items() if v == 1]
    return final[0]

这可能是一个解决方案，但性能得分只有50%。不确定是什么使其达到100%。如果您在Codility挑战中获得了100%的性能，请发布。

编辑1：

def solution(A):
    A.sort()
    A.append(-1) #Just to make list even and run till last but not match with existing integers
    for i in range(0,len(A),2):
        if A[i]!=A[i+1]:
            return A[I]

这让我获得了100%的性能分数。参考：CodeTrading（YouTube）

0
我用这个解决方案取得了百分之百的表现。
from collections import Counter

def solution(A):
    counter = Counter(A)
    for k,v in counter.items():
        if v % 2 == 1:
            return k
    return None
你的回答可以通过提供更多的支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的回答是否正确。你可以在帮助中心找到关于如何撰写好回答的更多信息。 - undefined
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接