当前位置: 首页 > 知识库问答 >
问题:

优化阵列的分区

嵇丰
2023-03-14

我当时正在解决一个编程挑战问题,但我的解决方案是对大量数据给出超时/错误。有人能帮我优化解决方案吗?

问题:

给你一个由N个整数组成的数组。现在需要固定X,使以下两个值之间的差值最小:

  1. A[1] * A[2] * A[3] * ......... * A[X]
  2. A[X+1] * A[X+2] * ........... * A[N]

如果X的值更多,则打印最小的一个。

约束:

  • <代码>1

输入:

  • 第一行包含整数N(表示大小)
  • 第二行包含空格分隔的数字(用于数组)
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。

共有2个答案

厉钊
2023-03-14

没有必要一遍又一遍地计算subArray的乘法。这就是您超时错误的原因。您使用Long存储乘法会导致错误的答案,您需要使用BigInteger。下面的方法只会做一次乘法。之后,您可以简单地迭代并找出它们之间的差异。

import java.math.BigInteger;
import java.util.Scanner;

public class ParitionArray {
    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 minIndex=0;
        BigInteger minNo=BigInteger.ZERO;
        BigInteger[] prefixedMult = new BigInteger[size];
        prefixedMult[0] = BigInteger.valueOf(arr[0]);
        for(int k =1; k< size; k++){
            prefixedMult[k] = prefixedMult[k-1].multiply(BigInteger.valueOf(arr[k]));
        }

        for(int k=0;k<size;k++){
            BigInteger part1 = prefixedMult[k]; //multiplication of A[1]*A[2]A[3].........*A[k]
            BigInteger part2 = prefixedMult[size-1].divide(part1);    //multiplication of A[k+1]A[k+2]...........*A[size]

            BigInteger diff = part1.subtract(part2).abs();
            if(k==0){
                minNo=diff;
                minIndex=k;
            }
            //System.out.println(diff);
            if(minNo.compareTo(diff)==1){
                minNo=diff;
                minIndex=k;
            }
        }
        System.out.println("MinNo: "+minNo+" Index: "+minIndex);
    }
}

输入:

5
2
8
6
5
3

输出:

MinNo: 74 Index: 1

我发现@AndrewScott的答案很有帮助。下面是它在Java中的等效实现:

 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 minIndex=0;
        Double minNo=Double.MAX_VALUE;
        Double[] prefixedMult = new Double[size];
        prefixedMult[0] = Math.log10((double)arr[0]);
        for(int k =1; k< size; k++){
            prefixedMult[k] = prefixedMult[k-1] + Math.log10((double)arr[k]);
        }

        for(int k=0;k<size;k++){
            Double part1 = prefixedMult[k]; //multiplication of A[1]*A[2]A[3].........*A[k]
            Double part2 = prefixedMult[size-1] - (part1);    //multiplication of A[k+1]A[k+2]...........*A[size]
            Double diff = Math.abs(part1 - part2);
            if(minNo > diff){
                minNo=diff;
                minIndex=k;
            }
        }
        System.out.println("MinNo: "+minNo+" Index: "+minIndex);
    }
程项禹
2023-03-14

尽管@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);

}
 类似资料:
  • 这是一个使用ValArray的简单c程序: 如果我像这样编译并运行它: 产出如预期: 但是,如果我像这样编译和运行它: 输出为: 如果使用优化参数,也会发生同样的情况。 GCC版本是(Archlinux最新版本): 但是,如果我尝试叮当,两者 和 产生相同的正确结果: clang版本是: 我还尝试了在Debian上使用GCC 4.9.2,其中可执行文件会产生正确的结果。 这是GCC中可能存在的错误

  • 本文向大家介绍Mysql优化之Zabbix分区优化,包括了Mysql优化之Zabbix分区优化的使用技巧和注意事项,需要的朋友参考一下 使用zabbix最大的瓶颈在于数据库,维护好zabbix的数据存储,告警,就能很好地应用zabbix去构建监控系统。目前zabbix的数据主要存储在history和trends的2个表中,随着时间的推移,这两个表变得非常大,性能会非常差,影响监控的使用。对MySQ

  • 本文向大家介绍MySQL分页优化,包括了MySQL分页优化的使用技巧和注意事项,需要的朋友参考一下 最近,帮同事重写了一个MySQL SQL语句,该SQL语句涉及两张表,其中一张表是字典表(需返回一个字段),另一张表是业务表(本身就有150个字段,需全部返回),当然,字段的个数是否合理在这里不予评价。平时,返回的数据大概5w左右,系统尚能收到数据。但12月31日那天,数据量大概20w,导致SQL执

  • 由于array1包含100多万个条目(即使其中70%是空/零条目),库文件(test.a)的大小相当大。 我知道使用哈希表只包含非空条目可以减少array1的大小,但是有没有办法在不更改的情况下压缩或优化库文件(test.a)的大小? 在struct中,在其他库中有很多地方可以访问的值,要更改当前的静态数组实现可能需要付出巨大的努力。

  • 本文向大家介绍Mysql优化技巧之Limit查询的优化分析,包括了Mysql优化技巧之Limit查询的优化分析的使用技巧和注意事项,需要的朋友参考一下 前言 在实际业务中对于分页来说是一个比较常见的业务需求。那么就会使用到limit查询,当我们在使用Limit查询的时候,在数据比较小、或者只查询前面一部分数据的时候效率是很高的。但是当数据量大的时候,或者查询offset数量比较大的时候,如:lim