我编写了一个代码来查找所有可能的数组子集的乘积.我得到了预期的输出,但是我无法让它足够快以清除时间相关的测试用例.
任何人都可以帮助我优化代码的速度吗？
第一个输入(testCases)是测试用例的数量.
根据测试用例的数量,我们将具有数组(大小)和数组元素(集合)的大小.
例如,有效输入将是：
1 3 2 3 5
哪里：
1is the number of testcases.3is the size of the test set and2 3 5are the elements of the input set.
预期的输出是：
71
上述输出的计算如下：
{2},{3},{5},{2,3},{3,5},3,5}
=> 2 3 5 6 15 10 30
=> 2 + 3 + 5 + 6 + 15 + 10 + 30
=> 71
import java.util.Scanner;
public class Test {
static int printSubsets(int set[]) {
int n = set.length;
int b = 0;
for (int i = 0; i < (1 << n); i++) {
int a = 1;
for (int j = 0; j < n; j++){
if ((i & (1 << j)) > 0) {
a *= set[j];
}}
b += a;
}
return b;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int testCases = scanner.nextInt();
for (int i = 0; i < testCases; i++) {
int size = scanner.nextInt();
int set[] = new int[size];
for (int j = 0; j < set.length; j++) {
set[j] = scanner.nextInt();
}
int c = printSubsets(set);
System.out.println((c - 1));
}
scanner.close();
}
}
解决方法
你需要使用一点数学.假设您有3个值,就像您的示例一样,但我们称之为A,B和C.
要获得产品总和,您需要计算：
Result3 = A + B + C + A*B + A*C + B*C + A*B*C
= A + B + A*B + (1 + A + B + A*B) * C
现在,如果我们先计算A B A * B,称之为Result2,那么你会得到：
Result2 = A + B + A*B Result3 = Result2 + (1 + Result2) * C
我们重复一遍,所以
Result2 = A + (1 + A) * B Result1 = A Result2 = Result1 + (1 + Result1) * B
你能看到这种模式吗？让我们使用4个值：
Result4 = A + B + C + D + A*B + A*C + A*D + B*C + B*D + C*D
+ A*B*C + A*B*D + A*C*D + B*C*D + A*B*C*D
= A + B + C + A*B + A*C + B*C + A*B*C
+ (1 + A + B + C + A*B + A*C + B*C + A*B*C) * D
= Result3 + (1 + Result3) * D
摘要：
Result1 = A Result2 = Result1 + (1 + Result1) * B Result3 = Result2 + (1 + Result2) * C Result4 = Result3 + (1 + Result3) * D
作为代码,这是：
private static long sumProduct(int... input) {
long result = 0;
for (int value : input)
result += (result + 1) * value;
return result;
}
只有一次迭代,所以O(n).
测试
System.out.println(sumProduct(2,3)); System.out.println(sumProduct(2,5)); System.out.println(sumProduct(2,5,7));
产量
11 71 575
UPDATE
也可以使用带有Lambda表达式的Java 8 Streams使用IntStream.of(int...)或Arrays.stream(int[])(它们执行相同操作)来完成代码.
// Using IntStream with result as int
private static int sumProduct(int... input) {
return IntStream.of(input).reduce((a,b) -> a + (1 + a) * b).getAsInt();
}
// Using Arrays with result as long
private static long sumProduct(int... input) {
return Arrays.stream(input)
.asLongStream()
.reduce((a,b) -> a + (1 + a) * b)
.getAsLong();
}
