小开

恒定的时间是不可能的。所有100万个数字都需要至少查看一次，因此这是 O (n)的时间复杂度，在本例中 n = 100万。

对于简单的 O (n)解决方案，创建一个大小为1000的数组，该数组表示每个可能的3位数的出现次数。每次前进1个数字，第一个索引 = = 0，最后一个索引 = = 99997，增量数组[3位数字]创建一个直方图(每个可能的3位数字的出现次数)。然后输出计数 > 1的数组内容。

小开

简单的 O (n)解决方案是计算每个3位数:

for nr in range(1000):
cnt = text.count('%03d' % nr)
if cnt > 1:
print '%03d is found %d times' % (nr, cnt)

这个程序可以将所有100万个数字搜索1000次。

只通过一次数字:

counts = [0] * 1000
for idx in range(len(text)-2):
counts[int(text[idx:idx+3])] += 1


for nr, cnt in enumerate(counts):
if cnt > 1:
print '%03d is found %d times' % (nr, cnt)

计时显示，只在索引上迭代一次的速度是使用 count的两倍。

小开

根据我的理解，你不可能在一个固定的时间内得到解决方案。它至少需要传递一次百万位数字(假设它是一个字符串)。您可以在百万长度数字的数字上进行3位滚动迭代，并且如果哈希键已经存在，则将其值增加1; 如果哈希键在字典中不存在，则创建一个新的哈希键(以值1初始化)。

代码如下所示:

def calc_repeating_digits(number):


hash = {}


for i in range(len(str(number))-2):


current_three_digits = number[i:i+3]
if current_three_digits in hash.keys():
hash[current_three_digits] += 1


else:
hash[current_three_digits] = 1


return hash

您可以向下筛选到项值大于1的键。

小开

我会解决以下问题:

def find_numbers(str_num):
final_dict = {}
buffer = {}
for idx in range(len(str_num) - 3):
num = int(str_num[idx:idx + 3])
if num not in buffer:
buffer[num] = 0
buffer[num] += 1
if buffer[num] > 1:
final_dict[num] = buffer[num]
return final_dict

应用到您的示例字符串时，这将产生:

>>> find_numbers("123412345123456")
{345: 2, 234: 3, 123: 3}

这个解决方案运行在 O (n)中，n 是所提供的字符串的长度，我想这是您能得到的最好结果。

小开

这里是一个“共识”O (n)算法的 NumPy 实现: 一边走一边遍历所有三元组和 bin。在遇到“385”时，通过向 bin [3,8,5]中添加一个 O (1)操作来完成分组。垃圾桶排列在一个 10x10x10立方体内。由于分类是完全向量化的，所以代码中没有循环。

def setup_data(n):
import random
digits = "0123456789"
return dict(text = ''.join(random.choice(digits) for i in range(n)))


def f_np(text):
# Get the data into NumPy
import numpy as np
a = np.frombuffer(bytes(text, 'utf8'), dtype=np.uint8) - ord('0')
# Rolling triplets
a3 = np.lib.stride_tricks.as_strided(a, (3, a.size-2), 2*a.strides)


bins = np.zeros((10, 10, 10), dtype=int)
# Next line performs O(n) binning
np.add.at(bins, tuple(a3), 1)
# Filtering is left as an exercise
return bins.ravel()


def f_py(text):
counts = [0] * 1000
for idx in range(len(text)-2):
counts[int(text[idx:idx+3])] += 1
return counts


import numpy as np
import types
from timeit import timeit
for n in (10, 1000, 1000000):
data = setup_data(n)
ref = f_np(**data)
print(f'n = {n}')
for name, func in list(globals().items()):
if not name.startswith('f_') or not isinstance(func, types.FunctionType):
continue
try:
assert np.all(ref == func(**data))
print("{:16s}{:16.8f} ms".format(name[2:], timeit(
'f(**data)', globals={'f':func, 'data':data}, number=10)*100))
except:
print("{:16s} apparently crashed".format(name[2:]))

毫不奇怪，NumPy 在大数据集上比@Daniel 的纯 Python 解决方案稍微快一点:

# n = 10
# np                    0.03481400 ms
# py                    0.00669330 ms
# n = 1000
# np                    0.11215360 ms
# py                    0.34836530 ms
# n = 1000000
# np                   82.46765980 ms
# py                  360.51235450 ms

小开

我的回答是:

from timeit import timeit
from collections import Counter
import types
import random


def setup_data(n):
digits = "0123456789"
return dict(text = ''.join(random.choice(digits) for i in range(n)))




def f_counter(text):
c = Counter()
for i in range(len(text)-2):
ss = text[i:i+3]
c.update([ss])
return (i for i in c.items() if i[1] > 1)


def f_dict(text):
d = {}
for i in range(len(text)-2):
ss = text[i:i+3]
if ss not in d:
d[ss] = 0
d[ss] += 1
return ((i, d[i]) for i in d if d[i] > 1)


def f_array(text):
a = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(10)]
for n in range(len(text)-2):
i, j, k = (int(ss) for ss in text[n:n+3])
a[i][j][k] += 1
for i, b in enumerate(a):
for j, c in enumerate(b):
for k, d in enumerate(c):
if d > 1: yield (f'{i}{j}{k}', d)




for n in (1E1, 1E3, 1E6):
n = int(n)
data = setup_data(n)
print(f'n = {n}')
results = {}
for name, func in list(globals().items()):
if not name.startswith('f_') or not isinstance(func, types.FunctionType):
continue
print("{:16s}{:16.8f} ms".format(name[2:], timeit(
'results[name] = f(**data)', globals={'f':func, 'data':data, 'results':results, 'name':name}, number=10)*100))
for r in results:
print('{:10}: {}'.format(r, sorted(list(results[r]))[:5]))

数组查找方法非常快(甚至比@paul-panzer 的 numpy 方法还要快!).当然，它是作弊的，因为它在完成之后技术上还没有完成，因为它返回了一个生成器。如果值已经存在，它也不必检查每次迭代，这可能会有很大帮助。

n = 10
counter               0.10595780 ms
dict                  0.01070654 ms
array                 0.00135370 ms
f_counter : []
f_dict    : []
f_array   : []
n = 1000
counter               2.89462101 ms
dict                  0.40434612 ms
array                 0.00073838 ms
f_counter : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_dict    : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
f_array   : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)]
n = 1000000
counter            2849.00500992 ms
dict                438.44007806 ms
array                 0.00135370 ms
f_counter : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_dict    : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
f_array   : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]

小开

最佳答案

你轻松脱身，你可能想为一家对冲基金工作，那里的定量分析师不懂基本的算法: -)

在 O(1)中，如果您需要访问每个元素至少一次，那么可以使用没有方法来处理任意大小的数据结构。在这种情况下，您希望的 最好的是 O(n)，其中 n是字符串的长度。

虽然，作为一个旁白，一个名义上的 O(n)算法威尔是 O(1)为一个固定的输入大小，所以，从技术上来说，他们可能是正确的这里。然而，人们通常不是这样使用复杂性分析的。

在我看来，你可以在很多方面给他们留下深刻印象。

首先，通知他们没有可以在 O(1)中完成，除非你使用上面给出的“可疑”推理。

其次，通过提供 Python 代码来展示你的精英技能，比如:

inpStr = '123412345123456'


# O(1) array creation.
freq = [0] * 1000


# O(n) string processing.
for val in [int(inpStr[pos:pos+3]) for pos in range(len(inpStr) - 2)]:
freq[val] += 1


# O(1) output of relevant array values.
print ([(num, freq[num]) for num in range(1000) if freq[num] > 1])

产出:

[(123, 3), (234, 3), (345, 2)]

当然，您可以根据需要修改输出格式。

最后，通过告诉他们 O(n)解决方案几乎肯定存在没有问题，因为上面的代码在不到半秒钟的时间内提供了一个100万位字符串的结果。它似乎也是线性伸缩的，因为一个10,000,000字符的字符串需要3.5秒，而一个100,000,000字符的字符串需要36秒。

而且，如果它们的需要比这个更好，有办法可以并行处理这类东西，可以大大加快速度。

由于 GIL 的原因，当然不在单身 Python 解释器中，但是您可以将字符串分割成类似下面这样的内容(为了允许对边界区域进行正确的处理，需要使用 vv指示的重叠) :

你可以把这些工作外包给不同的工人，然后再把结果合并起来。

分割输入和合并输出很可能会用小字符串(甚至可能是百万位字符串)淹没任何节省，但是，对于更大的数据集，这很可能会产生不同。当然，我惯用的 “测量，不要猜测”咒语也适用于这里。

这句箴言也适用于其他的各种可能性，比如完全绕过 Python，使用一种可能更快的不同语言。

例如，下面的 C 代码与前面的 Python 代码运行在相同的硬件上，在0.6秒内处理一个 100百万位数字，大致相当于 Python 代码处理一百万位数字的时间。换句话说，很多更快:

#include <stdio.h>
#include <string.h>


int main(void) {
static char inpStr[100000000+1];
static int freq[1000];


// Set up test data.


memset(inpStr, '1', sizeof(inpStr));
inpStr[sizeof(inpStr)-1] = '\0';


// Need at least three digits to do anything useful.


if (strlen(inpStr) <= 2) return 0;


// Get initial feed from first two digits, process others.


int val = (inpStr[0] - '0') * 10 + inpStr[1] - '0';
char *inpPtr = &(inpStr[2]);
while (*inpPtr != '\0') {
// Remove hundreds, add next digit as units, adjust table.


val = (val % 100) * 10 + *inpPtr++ - '0';
freq[val]++;
}


// Output (relevant part of) table.


for (int i = 0; i < 1000; ++i)
if (freq[i] > 1)
printf("%3d -> %d\n", i, freq[i]);


return 0;
}

小开

正如在另一个答案中提到的，您不能在常量时间内执行此算法，因为您必须查看至少 n 个数字。线性时间是最快的。

然而，该算法可以在 O (1) 空间中完成。您只需要存储每个3位数字的计数，因此您需要一个包含1000个条目的数组。然后您可以将数字流传入。

我的猜测是，要么是面试官在给你解决方案时说错了话，要么是你在他们说“恒定空间”时听错了“恒定时间”

小开

一百万对于我下面给出的答案来说是很小的。只要求你能够在面试中不间断地运用解决方案，那么以下方法将在不到两秒钟的时间内奏效，并给出所要求的结果:

from collections import Counter


def triple_counter(s):
c = Counter(s[n-3: n] for n in range(3, len(s)))
for tri, n in c.most_common():
if n > 1:
print('%s - %i times.' % (tri, n))
else:
break


if __name__ == '__main__':
import random


s = ''.join(random.choice('0123456789') for _ in range(1_000_000))
triple_counter(s)

希望面试官会希望使用标准库集合。

并行执行版本

我写了一个博客文章更多的解释。

小开

inputStr = '123456123138276237284287434628736482376487234682734682736487263482736487236482634'


count = {}
for i in range(len(inputStr) - 2):
subNum = int(inputStr[i:i+3])
if subNum not in count:
count[subNum] = 1
else:
count[subNum] += 1


print count

小开

图片作为答案:

IMAGE AS ANSWER

看起来像滑动窗户。

小开

我的解决办法是:

from collections import defaultdict
string = "103264685134845354863"
d = defaultdict(int)
for elt in range(len(string)-2):
d[string[elt:elt+3]] += 1
d = {key: d[key] for key in d.keys() if d[key] > 1}

在 for 循环中加入一点创造性(以及使用 True/False/Nothing 的附加查找列表) ，你应该能够去掉最后一行，因为你只想在我们访问过一次的 dict 中创建键。希望对你有所帮助:)

小开

- 从 C 的角度讲。 - 可以有一个 int 3-d 数组结果[10][10][10] ; - 从第0个位置到第 n-第4个位置，其中 n 是字符串数组的大小。 - 在每个地点，检查当前，下一个和下一个的下一个。 - 将 cntr 增量为 result [ current ][ next ][ next’s next ] + + ; - 列印

results[1][2][3]
results[2][3][4]
results[3][4][5]
results[4][5][6]
results[5][6][7]
results[6][7][8]
results[7][8][9]

这是 O (n)时间，没有任何比较。 - 你可以在这里运行一些并行的东西通过划分数组和计算周围的分区的匹配。

给定一个由一百万个数字组成的字符串，返回所有重复的3位数字

并行执行版本