Сумма частных, когда все элементы массива делятся на элементы каждого массива.

Question

В тесте кодирования наткнулся на вопрос, предположим, у нас есть массив, arr = [4,3,8].Разделив массив на 4, получим 1 (4/4) + 0 (3/4) + 2 (8/4) = 3. Аналогично, на 3 получим 4, а на 8 - 1. Таким образом, на выходе получим 3 + 4 + 1 = 8. O(n2) решение дало TLE, поэтому я попытался сделать лучше.

Я думал о сортировке и использовании нижней границы.Нижняя граница arr[i]*k, для k = 1,2,3..., до arr[i]*k<=max(arr), даст мне количество элементов больше, чем взятый кратный, это добавит в конечном результате.Но это дало мне неправильный ответ.Как я могу эффективно решить эту проблему, любые предложения приветствуются.

Answer 1

Если я правильно понимаю ваш вопрос, вы хотите (в этом примере) три массива, которые являются массивом оригиналов, разделенных (с делением целых чисел) на каждый из трех его элементов, а затем суммируют их.

arr = [4,3,8]
sum([el//i for i in arr for el in arr])

даст вам желаемый результат.Для понимания, результирующий список имеет вид:

In [8]: [el//i for i in arr for el in arr]
Out[8]: [1, 0, 2, 1, 1, 2, 0, 0, 1]

Суммирование по этому дает результат 8.Если вам действительно нужны три массива отдельно и не объединены таким образом, я отредактирую этот ответ.

РЕДАКТИРОВАТЬ Поэтому я неправильно понял вопрос, извините.Если вам разрешено использовать numpy, я бы предложил этот алгоритм, который (я думаю) все еще является O (n²), но в целом гораздо быстрее:

arr = np.random.randint(1,10,n)
np.sum(np.tile(arr, n)//np.repeat(arr,n))

Может быть, я смогу придумать что-нибудь более умное завтра

РЕДАКТИРОВАТЬ 2 Сортировка на самом деле является хорошей идеей и немного ускоряет алгоритм.До сих пор я тестировал три решения с помощью этого маленького сценария (я знаю, что time.time не подходит для точного времени, но он просто показывает общую скорость каждого алгоритма):

for n in range(100, 500):
    arr = np.random.randint(1,10,n)
    #sorted
    t = time.time()
    arr2 = sorted(arr)
    sum([el1//el2 for i, el2 in enumerate(arr2) for el1 in arr2[i:]])
    t2 = time.time()-t
    times_sorted.append(t2)

    #standard
    t = time.time()
    arr = sorted(arr)
    sum([el1//el2 for el2 in arr for el1 in arr])
    t2 = time.time()-t
    times_standard.append(t2)

    #numpy
    t = time.time()
    arr = sorted(arr)
    np.sum(np.tile(arr, n)//np.repeat(arr, n))
    t2 = time.time()-t
    times_numpy.append(t2)
    if not n%50:
        print(n)

Печать с

plt.figure()
plt.plot(times_numpy)
plt.plot(times_sorted)
plt.plot(times_standard)
plt.legend(["numpy", "sorted", "standard"])
plt.xlabel("n")
plt.ylabel("time in s")

Дает: