谦逊OddOccurrencesInArray问题-递归和Python
我试图使用递归来解决谦卑中的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终止的测试程序)
有人能帮我弄清楚这意味着什么吗？算法上，我认为我的解决方案是合理的，我不明白为什么它不返回我指定的整数值。
回答 6
Stack Overflow用户
发布于 2022-01-05 19:07:09
我建议采取完全不同的办法。递归方法并不是不正确的，但是对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 elementanswer = solve(input)
if answer is None:
print("no solution")
else:
print("the solution is", answer)Stack Overflow用户
发布于 2022-02-01 09:25:44
另一个Python解决方案100%
还有另一种解决方案，我们可以使用XOR逻辑。
首先，让我们一起记住XOR是什么意思：
因此，我们可以认识到，如果对于输入A、和输入B-有相同的位，则异或输出将为零。
另外，如果我们取零的任何数字的位异或，肯定会给出相同的数字，因为这个数字的位会产生相同的位，这意味着相同的数字。
现在，为了解决XOR逻辑的问题，我们首先定义一个数字，这个数字每次都保存着XOR输出的结果，所以首先，我们从零开始，我在前面说过，任何数字的0都会给出相同的数字。
但是，如果我们下次得到一个不同的数字，XOR的结果将是一些未知的数字。
最后，没有对的数字肯定会被返回。
因为这样的解决方案只需要一个循环，我们就需要遍历所有的元素，如果我们在某个点执行断开，则XOR的结果将是一些我们不需要的数字，因此我们需要确保遍历整个数组一次，然后因为相同数字的位XOR将返回零。这样我们就能保持在与任何事物都不成对的数字的末尾。
检测时间复杂度：O(N)或O(N*log(N))
def solution(A):
num = 0
for i in range(len(A)):
num = num ^ A[i]
return numStack Overflow用户
发布于 2022-01-05 18:47:30
您不会从递归调用中返回任何内容，这意味着您将返回None。
https://stackoverflow.com/questions/70598062
复制相似问题
腾讯云开发者
