查找列表中所有元素共享至少一个相同数字的最大可能计数



给出包含数字的数组存在一个问题,该语句是找到由给定数组形成的子序列的最大长度,以便该子序列中的所有元素共享至少一个公共数字。

现在有什么收获?好吧,我打算使用字典b将键存储为到目前为止的每个数字和值,同时逐个数字遍历给定的数组。我认为字典值中的最大数量,即更大的数字计数将是问题答案,因为我们仍然有一个故障,我们不应该计算数组的一个元素中存在的相同数字不止一次。为了克服这个故障,我使用了 setc.

为了方便起见,为此编写了代码函数以及下面编写的驱动程序函数。

def solve (a):
b={}
answer=1
for i in a:
j=i
c=set()
c.clear()
while(j):
last_digit=i%10
if(last_digit not in b and last_digit not in c):
b[last_digit]=1
c.add(last_digit)
elif(last_digit in b and last_digit not in c):
b[last_digit]+=1
c.add(last_digit)
answer=max(answer,b[last_digit])
j//=10
return answer

a=list(map(int,input().strip().split()))
print(solve(a))

有很多测试用例关注此代码是否正确。其中之一是输入是12 11 3 4 5,代码给出的输出是1的,预期的输出是2。什么给?

你有好主意。但是,如果使用collections模块中的Counter对象,则代码会更容易。它旨在执行您尝试执行的操作:计算可迭代对象中项的出现次数。

此代码使用生成器表达式查看列表alist中的每个值,使用内置str()函数将该整数转换为数字字符串,然后使用set()内置函数将其转换为集合。正如您所说,这将删除重复的数字,因为您只想为每个项目计算每个数字一次。然后,Counter对象查看这些数字并计算它们的出现次数。然后,代码使用Countermost_common方法来选择出现最多的数字((1)参数仅返回列表中最流行的单个数字,0索引将该数字及其计数从列表中取出),然后获取该数字的计数(即1索引)。然后,该计数将返回给调用方。

如果您不熟悉Counter或生成器表达式,您可以自己进行计数并使用常规for循环。但是这段代码很短,对于任何知道Counter对象的人来说都相当清楚。如果你想要简短的代码,你可以使用注释中的行来替换以下四行,但我扩展了代码以使其更清晰。

from collections import Counter

def solve(alist):
digitscount = Counter(digit for val in alist for digit in set(str(abs(val))))
# return digitscount.most_common(1)[0][1]
most_common_list = digitscount.most_common(1)
most_common_item = most_common_list[0]
most_common_count = most_common_item[1]
return most_common_count

alist = list(map(int, input().strip().split()))
print(solve(alist))

对于您的示例输入12 11 3 4 5,这将打印正确答案2。请注意,如果输入为空或包含非整数,我的代码将给出错误。此版本的代码采用列表值的绝对值,这可以防止减号(或负号)计为数字。

这是我自己的实现:

def solve(list_of_numbers):
counts = {str(i):0 for i in range(10)}  # make a dict of placeholders 0 through 9
longest_sequence = 0                    # store the length of the longest sequence so far
for num in list_of_numbers:             # iterate through our list of numbers
num_str = str(num)                  # convert number to a string (this makes "is digit present?" easier)
for digit, ct in counts.items():    # evaluate whether each digit is present
if digit in num_str:            # if the digit is present in this number...
counts[digit] += 1          # ...then increment the running count of this digit
else:                           # otherwise, we've broken the sequence...
counts[digit] = 0           # ...so we reset the running count to 0.
if ct > longest_sequence:       # check if we've found a new longest sequence...
longest_sequence = ct       # ...and if so, replace the current longest sequence
return longest_sequence[1]              # finally, return the digit that had the longest running sequence.

它使用dict来存储每个数字连续出现的运行计数 - 对于每个数字,如果数字存在,则计数递增,如果不存在,则重置为 0。到目前为止,最长序列的长度保存在其自己的变量中以供存储。

我认为,您的实现忽略了一些细节:

  1. 您的代码可能返回出现次数最多的数字,而不是出现次数最多的数字。我不确定,因为您的代码对我来说很难解析,而且您只给出了一个测试示例。
  2. 如果可以的话,尽量避免使用单字母变量名称。请注意,我的上述代码更加清晰,因为我使用了全名(最坏的情况是,清晰的缩写,如"count"的ct)。这使得调试自己的代码变得更加容易。
  3. 我知道您正在做什么来查找数字中存在的数字,但这比情况需要的要详细一些。我使用的一个更简单的解决方案是简单地将数字转换为字符串,并使用每个数字的字符而不是其值。在你的实现中,你可以做这样的事情:c = set(int(digit) for digit in str(j))
  4. 您的代码中似乎没有任何内容可以检测数字何时不再存在,这可能会导致不正确的结果。

我无法理解原始问题,但我认为您需要做的是将每个项目转换为字符串(如果它是 int),然后拆分每个数字。

digits = {}
for item in thelist:
digit[item] = []
if len(item) > 1:
for digit in str(item):
digits[item].append(int(digit))

如果您的测试用例12 11 3 4 5那么这将生成一个{12 : [1,2], 11 : [1,1], etc}字典

最新更新