我正在解决一个编程挑战问题,但我的解决方案是给出大量的超时/错误。谁能帮我优化我的解决方案?
问题:
You are given an array A of N integers. Now you are required to fixed X such that the difference between the following two values is minimum:
1. A[1] * A[2] * A[3] * ......... * A[X] 2. A[X+1] * A[X+2] * ........... * A[N]
and if there is more value of X then print the smallest one.
Constraint:
1 <= 1 <= 10^5
1 <= A[i] <= 10^18
Input:
- The first line contains integer N (for size)
- The second line contains space separated numbers (for array)
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner s=new Scanner(System.in)
int size=Integer.parseInt(s.nextLine);
long arr[]=new long[size];
for(int i=0;i<=size;i++){
arr[i]=s.nextLong();
}
long part1=1,part2=1;
long diff=1;long minIndex=0;long minNo=0;
for(int k=0;k<size-1;k++){
part1=1;part2=1;
//minIndex=k;
for (int i=0;i<=k ; i++){
part1=part1*arr[i];
}
for(int j=k+1;j<=size;j++){
part2=part2*arr[j];
}
//System.out.println(part1+"---"+part2);
diff=Math.abs(part1-part2);
if(k==0){
minNo=diff;
minIndex=k;
}
//System.out.println(diff);
if(minNo>diff){
minNo=diff;
minIndex=k;
}
}
System.out.println("MinNo: "+minNo+" Index: "+minIndex);
}
}
我正在测试这个输入
5
9090909090909009 780009090900909 898989898898898 98998 9999776765576765
答案应该是 2(如果从零开始计数,则为 1)但我的代码给出的是 4。
最佳答案
虽然@Mukesh Prajapati 建议的答案有效,但仍然有更快更好的方法来做到这一点。
您可以使用 log
来缩短值,这样您就可以在 log
计算中添加或减去值,因为现在加法意味着乘法,减法意味着分配。现在您的问题简化为在数组中找到一个点,其中左侧元素的总和最接近右侧元素。
您存储累积总和以便快速查找。这使您能够快速计算数组的左和和右和。最终的最小差异在 ans
中,而索引在 index
变量中。
void partition(int n, vector<double> &a) {
double total = 0; vector<double> sum_array_a;
for(auto &x: a) {
x = log10(x);
total += x;
sum_array_a.push_back(total);
}
double ans = INFINITY, index = -1;
for(int i = 0; i < n; i++) { // Check for all points if you can split here
double left = sum_array_a[i];
double right = total - left; // Right side sum of elements
double diff = abs(left - right);
if(diff < ans) {
ans = diff;
index = i;
}
}
printf("%f", index);
}
关于java - 优化数组的分区,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55894077/