logo标签列表

寻找奇偶异常值，CodeWars Python问题

pythonpython-3.x
3

我正在尝试解决这个问题，但我没有得到正确的答案。下面是问题的描述：

给定一个包含整数的数组（长度至少为3，但可能很大）。该数组要么完全由奇数组成，要么完全由偶数组成，但有一个例外，即单个整数N不同于其他整数。编写一种方法，将数组作为参数并返回此“离群值”N。

以下是我的代码：

a = [2, 4, 6, 8, 10, 3]
b = [2, 4, 0, 100, 4, 11, 2602, 36]
c = [160, 3, 1719, 19, 11, 13, -21]

def find_outlier(list_integers):
    for num in list_integers:
       if num % 2 != 0:
         odd = num
       elif num % 2 == 0:
         even = num
    for num in list_integers:
      if len([odd]) < len([even]):
        return odd
      else:
        return even


print(find_outlier(a))

print(find_outlier(b))

print(find_outlier(c))

它输出10、36、160 ，显然只有最后一个是正确的。 有人可以帮我解决吗？ 谢谢！

1
len([odd]) 不可能返回除 1 以外的任何值 - 因为你明确地将一个只有一个元素的列表传递给了函数！ - jasonharper
1
这回答解决了您的问题吗？[在奇数/偶数整数列表中查找奇偶校验异常值] (https://stackoverflow.com/questions/39089459/finding-the-parity-outlier-in-a-list-of-odd-even-integers) - Georgy
1
另外：查找奇偶性异常值 Python - Georgy
5个回答
4

如果存在异常值，您可以分析前三个并找到异常值。 如果有，你就完成了。如果没有，你知道期望的奇偶性，并可以相应地测试每个后续元素。

为奇/偶数创建列表，在原则上会导致结果，但不必要地浪费内存。

在代码中，这可能看起来像：

def find_outlier(seq):
    par0 = seq[0] % 2
    par1 = seq[1] % 2
    if par0 != par1:
        return seq[1] if seq[2] % 2 == par0 else seq[0]
    # the checks on the first 2 elements are redundant, but avoids copying
    # for x in seq[2:]: would do less iteration but will copy the input
    for x in seq:  
        if x % 2 != par0:
            return x


a = [2, 4, 6, 8, 10, 3]
b = [2, 4, 0, 100, 4, 11, 2602, 36]
c = [160, 3, 1719, 19, 11, 13, -21]

print(find_outlier(a))
# 3
print(find_outlier(b))
# 11
print(find_outlier(c))
# 160

你的代码以目前的形式无法正常工作：

  • 这个代码块：
    for num in list_integers:
       if num % 2 != 0:
         odd = num
       elif num % 2 == 0:
         even = num

您将只在odd中看到最后一个奇数，而在even中看到最后一个偶数，没有任何关于有多少个数字的信息。 您需要计算有多少个偶数/奇数，并最终需要存储遇到的每个奇偶性的第一个值。

  • 这是第二个区块
    for num in list_integers:
      if len([odd]) < len([even]):
        return odd
      else:
        return even

代码总是检查长度为length-1的列表，并始终返回even。

我没有看到简单的修复方式，可以使您的代码与上述解决方案具有可比较的效率。但是您可以调整您的代码以使其合理高效（时间复杂度为O(n)，但不带短路功能；空间复杂度为O(1)）：

def find_outlier_2(seq):
    odd = None
    even = None
    n_odd = n_even = 0
    for x in seq:
        if x % 2 == 0:
            if even is None:  # save first occurrence
                even = x
            n_even += 1
        else:  # no need to compute the modulus again
            if odd is None:  # save first occurrente
                odd = x
            n_odd += 1
    if n_even > 1:
        return odd
    else:
        return even

上述方法比其他答案更有效，因为它不会创建不必要的列表。 例如，这些 解决方案 在时间复杂度和空间复杂度上都消耗更多内存（时间复杂度为 O(n)，空间复杂度也为 O(n)）：
def find_outlier_3(list_integers):
    odd = []
    even = []
    for num in list_integers:
       if num % 2 != 0:
         odd.append(num)
       elif num % 2 == 0:
         even.append(num)
    if len(odd) < len(even):
      return odd[0]
    else:
      return even[0]


def find_outlier_4(lst):
    odds = [el % 2 for el in lst]
    if odds.count(0) == 1:
        return lst[odds.index(0)]
    else:         
        return lst[odds.index(1)]

简单的基准测试表明，这些解决方案的速度也更慢：

%timeit [find_outlier(x) for x in (a, b, c) * 100]
# 10000 loops, best of 3: 128 µs per loop
%timeit [find_outlier_2(x) for x in (a, b, c) * 100]
# 1000 loops, best of 3: 229 µs per loop
%timeit [find_outlier_3(x) for x in (a, b, c) * 100]
# 1000 loops, best of 3: 341 µs per loop
%timeit [find_outlier_4(x) for x in (a, b, c) * 100]
# 1000 loops, best of 3: 248 µs per loop
这个函数最后三行的结果将与 return [x for x in seq[3:] if x % 2 != par0][0] 相同，但我理解这个一行代码不必遍历整个列表（尽管其中有“for x in seq[3:]”），因为它在列表推导内包含了条件。我的理解是否错误？这两者的时间复杂度相同吗？ - patmcb
@patmcb，你的一行代码（列表推导式）将遍历seq[3：]的所有元素。相比之下，我的答案中的代码将在满足条件时立即停止迭代。 - norok2
此外，如果追求速度，对于足够大的输入，“for x in seq[3：]”将比“for x in seq：”慢，因为前者本质上是创建了一个“seq”的副本，可以通过增加3次迭代来避免这种情况。 - norok2
1
@norok2 感谢澄清。这完全有道理。而你的代码之所以在满足条件时停止，是因为return的工作原理，对吗？ - patmcb
1
我认为 seq[3:] 应该真正是 seq[2:]（或 seq），否则，如果前两个具有相同的奇偶性，而第三个没有，则会被忽略。 - Idea O.
显示剩余2条评论
3
你可以很好地使用列表推导式来实现这个功能：
a = [2, 4, 6, 8, 10, 3]
b = [2, 4, 0, 100, 4, 11, 2602, 36]
c = [160, 3, 1719, 19, 11, 13, -21]

def outlier(lst):
    odds = [ el % 2 for el in lst ]    # list with 1's when odd, 0's when even
    print(odds)                        # just to show what odds contains
    if odds.count(0) == 1:             # if the amount of zeros (even numbers) = 1 in this list
        print(lst[odds.index(0)])      # find the index of the 'zero' and use it to read the value from the input lst
    else:         
        print(lst[odds.index(1)])      # find the index of the 'one' and use it to read the value from the input lst

outlier(a)
outlier(b)
outlier(c)

输出

[0, 0, 0, 0, 0, 1]        # only 1 'one' so use the position of that 'one'
3
[0, 0, 0, 0, 0, 1, 0, 0]  # only 1 'one' so use the position of that 'one'
11
[0, 1, 1, 1, 1, 1, 1]     # only 1 'zero' so use the position of that 'zero'
160
请注意，这个问题的解决方案在时间和内存上都是O(N)，虽然有可能用O(N)的时间和O(1)的内存来解决。 - norok2
2

我想，首先通过查看一个小样本来确定离群值是奇数还是偶数，然后使用列表推导式仅返回离群值可能更加有效。这样，如果列表很大，就不会出现超时问题。

以下是我的做法：

def findoutlier(yourlist):
    if (yourlist[0] % 2 == 0 and yourlist[1] % 2 == 0) or (yourlist[0] % 2 == 0 and yourlist[2] % 2 == 0) or (yourlist[1] % 2 == 0 and yourlist[2] % 2 == 0):
        oddeven = "even"
    else:
        oddeven = "odd"
    if oddeven == "even":
        return [i for i in yourlist if i % 2 != 0][0]
    else:
        return [i for i in yourlist if i % 2 == 0][0]

a = [2, 4, 6, 8, 10, 3]
b = [2, 4, 0, 100, 4, 11, 2602, 36]
c = [160, 3, 1719, 19, 11, 13, -21]

print(findoutlier(a))
print(findoutlier(b))
print(findoutlier(c))

这将会按预期返回3、11和160。
2

统计列表中前三个元素中奇数值的数量。可以使用 sum() 函数完成此操作。如果总和 > 1，则该列表主要包含奇数，因此找到偶数异常值。否则找到奇数异常值。

def find_outlier(sequence):
    if sum(x & 1 for x in numbers[:3]) > 1:

        # find the even outlier
        for n in sequence:
            if not n & 1:
                return n

    else:
        # find the odd outlier
        for n in sequence:
            if n & 1:
                return n
1

您希望使用列表来存储您的奇数/偶数。目前，您将它们存储为int，并且它们在循环的下一次迭代中被替换。

def find_outlier(list_integers):
    odd = []
    even = []
    for num in list_integers:
       if num % 2 != 0:
         odd.append(num)
       elif num % 2 == 0:
         even.append(num)
    if len(odd) < len(even):
      return odd[0]
    else:
      return even[0]
1
谢谢你的帮助！ 我本以为会是这样，但当我创建一个空列表时，它会在列表中给出第一个整数 a, b, c。 - Hamza Ahmed
你能否更新你的问题并附上空列表的代码？或者你是指使用我发布的上述代码得到了那个结果？ - raccoons
1
我用你上面发布的代码得到了结果！哈哈，抱歉让你困惑了！ - Hamza Ahmed
我的错，没有看到你在原始代码中调用 len 的方式。更新后的版本现在应该可以工作了。 - raccoons
2
请注意，这个方法过于复杂。最简单的改进是用简单的 if num % 2 != 0: ... else: ... 替换 if num % 2 != 0: ... elif num % 2 == 0: ...。第二个问题是，这个解决方案需要额外的 O(n) 内存，而没有特别好的理由，因为它将输入中的所有数字存储在两个单独的列表中，但然后对于每个奇偶性，它只使用了最先遇到的数字。 - norok2
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接