数组分为两部分,两个数组的和相差最小

昨天一朋友问我面试题,从一个数组里,分成两个数组,两个数组的数字相加的和相差最小?

【问题】将数组分为两部分,使得两部分的和最接近,返回两部分的差值。例如:

int[] array={1,0,1,7,2,4},分为两部分为{1,0,1,2,4},{7},差值为1。

发现一个明了暴力不简单的方法,分享出来大家看一下

public static void main(String[] args) {
    //随便一个数组
    int as[] = new int[]{1,1,1,1,4,6,4,3,2,4,14,342,4234,5243,52,345,23,45,23,45,23,45,32,45,234,52,4,5,345,34,5,234,52,345,23,54,2345,32,45,23,5423,45,23,45,234,523,45,23,45,234,523,45,234,523,45,32,545,4,5,5555,545,5453};
    int[] a =  new int[]{};
    int[] b =  new int[]{};
    numss(as,a,b);
}

public static void numss(int[] as,int[] a,int[] b){
    if (a.length > 0 && b.length > 0 ){
        Integer asum = sum(a);
        Integer bsum = sum(b);
        Boolean aflag = false;
        Boolean bflag = false;
        //如果过a数组的i个元素给了b之后,两个数组的差最小
        for (int i=0;i<=a.length-1;i++){
            if ( Math.abs( (asum-a[i]) - (bsum+a[i]) ) < Math.abs(sum(a) - sum(b)) ){
                b = Arrays.copyOf(b,b.length+1);
                b[b.length-1] = a[i];
                a = removeIndex(a,i);
                aflag = false;
                break;
            }else{
                aflag =true;
            }
        }
        //如果过b数组的i个元素给了a之后,两个数组的差最小
        for (int i=0;i<=b.length-1;i++){
            if ( Math.abs( (bsum-b[i]) - (asum+b[i]) ) < Math.abs(sum(a) - sum(b)) ){
                a = Arrays.copyOf(a,a.length+1);
                a[a.length-1] = b[i];
                b = removeIndex(b,i);
                bflag = false;
                break;
            }else{
                bflag = true;
            }
        }
        //如果两个数组都没有合适的数字给对方就输出,否则回调
        if (aflag && bflag){
            System.out.println("a为");
            for (int s : a){
                System.out.print("    "+s);
            }
            System.out.println();
            System.out.println("b为");
            for (int s : b){
                System.out.print("    "+s);
            }
            System.out.println();
            System.out.println("差为:"+ Math.abs(bsum - asum));
        }else{
            numss(as,a,b);
        }
    }else{
        int index = as.length / 2 ;
        a = Arrays.copyOf(as, index);
        b = Arrays.copyOfRange(as, index, as.length);
        numss(as,a,b);
    }
}
//数组求和
public static Integer sum(int[] a){
    int sum=0;
    int Max=a[0],Min=a[0];
    for(int i=0;i<a.length;i++){
        sum+=a[i];
    }
    return sum;
}
//数组删除指定下标
public static int[] removeIndex(int[] arr,int x){
    arr[x] = arr[arr.length-1];
    arr = Arrays.copyOf(arr, arr.length-1);
    return arr;
}

运行截图:

数组分为两部分,两个数组的和相差最小

数组分为两部分,两个数组的和相差最小

喜欢(4) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下吧

支付宝扫一扫打赏

微信扫一扫打赏