查找要由给定数字替换的数组中的元素数，使得数组的总和小于另一个给定数

Question

我需要一些问题的帮助。假设你有一个排序数组“A”，它有“N”个元素和两个整数“X”和“Y”。现在要求两个人找到“A”中的元素数量，你必须用“X”代替，这样数组“A”的总和小于“Y”。使用以下技术可以在O（n ^ 2）中轻松解决给定的问题。（仅针对此的代码片段是特定操作）。

sum = None
count = None
for i in range(N):
   for j in range(i):
        A[j] = X
        count += 1
   for k in range(N):
        sum += A[k]
   if sum==Y:
        print(count)
        count = 0
        break

但我希望以更有效的方式做到这一点，有人可以建议一种更有效的方式吗？提前致谢

Answer 1

由于您的数组已排序，您可以：

1. 计算你的数组之和（O（n））
2. 检查是否满足saved_sum <= Y（O（1））
3. 从最后/第一个位置开始（取决于最大值的位置） 3.1检查该值是否大于X，如果不是，则无法进一步减少A的总和 3.2用X替换并用values-x减少saved_sum 3.3检查saved_sum是否<= Y，如果不重复，则在3.1中以A的第二大值重复

整个事物在O（n）中运行，因为A是有序的，最大/下一个最大可以在O（1）中找到