请教一道java面试题

随便找一种分法就驳倒你的结论
A（4，7，11，21，9） B（5，4，13，15，12）
A组的和是52 B组的和是49 A-B=3

2n个数每个数轮流做分界点,求出该分界点下 A B两组的差...然后分界点为key ,差为value 用一个map来保存...最后在map中查找value最小的,找到相应的key..
也可以不用map,申明一个变量跟踪最小值...直接得到key

import java.util.Arrays;public class Test { final static int[] NUMS = new int[]{4,7,11,21,5,4,9,13,15,12};

public static void main(String[] args) {
getMin();
} static void getMin() {
Arrays.sort(NUMS);
int[] groupA = new int[NUMS.length / 2];//set small nums
int[] groupB = new int[NUMS.length / 2];//set big nums
System.arraycopy(NUMS, 0, groupA, 0, groupA.length);
System.arraycopy(NUMS, NUMS.length / 2, groupB, 0, groupB.length);
int min = Integer.MAX_VALUE;
for(int i = 0;i < groupA.length;i++){
for(int j = groupB.length - 1;j >= 0;j--){
int minus = Math.abs((getSum(groupA,groupB[j],groupA[i]) - getSum(groupB,groupA[i],groupB[j])));
if(minus <= min){
int temp = groupB[j];
groupB[j] = groupA[i];
groupA[i] = temp;
min = minus;
}
}
}
System.out.println("Total sum = " + getSum(NUMS));
print(groupA);
print(groupB);
System.out.println("Min value = " + Math.abs(getSum(groupA) - getSum(groupB)));
}

static int getSum(int numbers[]){
return getSum(numbers, 0, 0);
}

static int getSum(int[] numbers,int add,int minus){
int sum = 0;
for(int i = 0;i < numbers.length;i++)
sum += numbers[i];
sum = sum + add - minus;
return sum;
}

static void print(int[] numbers){
int sum = 0;
for(int i = 0;i < numbers.length;i++){
System.out.print(numbers[i] + " ");
sum += numbers[i];
}
System.out.println("sum = " + sum);
}

}

先进行从大到小的排列，取出中间的5个为A，剩下的5个为B，求出十个数相加的平均值Sum，再求出A和B的和SumA SumB，他SumA - Sum和SumB - Sum值a肯定是一样的，从A和B中找出两个数的差和a最接近就行了，因为都是整数，所以a肯定为X或者X.5，我们找出A和B中差为X或者（X+1）替换即可。
楼主的例子步骤如下：
1.先排序：21 15 13 12 11 9 7 5 4 4
2.分出A和B：A：13 12 11 9 7 B：21 15 5 4 4
3.平均值为Sum = 50.5 SumA = 52，SumB = 49，所以差值a = 1.5，所以找出B中的值减去A中的值为1或2，交换，发现有7和5（如果没有则找差为3或者0的两个数，依次类推），交换后 A：13 12 11 9 5 Ｂ:21 15 7 4 4，即得出结果。

下边是源代码：
import java.util.*;
public class Test
{
public int[] intTest;
public int sizeArray;
public int[] A;
public int[] B;
//int avr;
public static void main(String[] args)
{
Test test = new Test(10);
test.initArray();
test.getSubArray();
for(int i = 0;i < test.sizeArray/2;i++)
{
System.out.print(test.A[i] + " ");
}
System.out.print("\n");
for(int i = 0;i < test.sizeArray/2;i++)
{
System.out.print(test.B[i] + " ");
}
}
public void initArray()
{
Scanner sc = new Scanner(System.in);
for(int i =0;i < this.sizeArray;i++)
{
intTest[i] = sc.nextInt();
}
}
public void sortArray(int[] intTest)
{
Arrays.sort(intTest);
}
Test(int n)
{
this.sizeArray = n;
intTest = new int[n];
A = new int[n/2];
B = new int[n/2];
}
public void getSubArray()
{
this.sortArray(this.intTest);//对数组进行排列
System.arraycopy(this.intTest,(this.sizeArray/2 + 1)/2,this.A,0,this.sizeArray/2);
System.arraycopy(this.intTest,0,this.B,0,(this.sizeArray/2 + 1)/2);
System.arraycopy(this.intTest,(this.sizeArray/2 + 1)/2 + this.sizeArray/2,this.B,(this.sizeArray/2 + 1)/2,this.sizeArray/4);
int sumA = this.getSum(this.A,this.sizeArray/2);//得到A数组中的各个元素的和
int sumB = this.getSum(this.B,this.sizeArray/2);//得到B数组中的各个元素的和
float sumAvr = (float)(sumA + sumB)/2;//得到数组A和数组B的平均值
int findNum1 = sumA - (int)sumAvr;//得到第一个要找的值（A中一个元素和B中一个元素的差值）
//int findNum2 = sumB - (int)sumAvr;
int findNum2 = findNum1 - 1;//得到第二个要找的值（A中一个元素和B中一个元素的差值）
do
{
for(int i = 0; i < this.sizeArray/2;i++)
{
for(int j = 0;j < this.sizeArray/2;j++)
{
if(this.A[i] - this.B[j] == findNum1 ||
this.A[i] - this.B[j] == findNum2)
{
int temp = this.A[i];
this.A[i] = this.B[j];
this.B[j] = temp;
return;
}
}
}
findNum1++;
findNum2--;
}
while(findNum1 == 0 || findNum1 == Math.abs(sumB - sumA));
}
public int getSum(int[] array,int n)
{
int sum = 0;
for(int i = 0;i < n;i++)
{
sum = sum + array[i];
}
return sum;
}
}

有规定一定是n个一组吗？如果是这样，从小到大排序，然后首尾首尾分别取，直到取出n个作为一组，剩余中间n为一组，这样应该最小吧
如果不是，可用排列组合法，在每个数前加上[+或-]，然后求和，取最小的组合

代码例子
import java.util.*;
public class Test {
    public static void main(String[] args) throws Throwable {
        minSumCombine(new int[]{4, 7, 11, 21, 5, 4, 9, 13, 15, 12});
    }    public static List<List<Integer>> minSumCombine(int[] a) {
        int n = a.length / 2;
        int[] dig = new int[a.length]; //2进制标识，0代表正，1代表负，求出各种01组合
        int cnt = 0, sum = 0, min = Integer.MAX_VALUE, nmin = Integer.MAX_VALUE;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i=0; i<4; i++) {
            result.add(new ArrayList<Integer>());
        }        while (dig[0] < 2) {
            sum = 0;
            cnt = 0;
            for (int i=0; i<a.length; i++) {
                if (dig[i] == 0) cnt++;
                sum += (dig[i] == 0 ? a[i] : -a[i]); //各种01组合求和
            }
            sum = Math.abs(sum);
            if (sum < min) { //任意个元素分组的情况
                min = sum;
                result.get(0).clear();
                result.get(1).clear();
                for (int i=0; i<a.length; i++) {
                    if (dig[i] == 0) {result.get(0).add(a[i]);}
                    else {result.get(1).add(a[i]);}
                }
            }
            if (cnt == n && sum < nmin) { //n个元素分组的情况
                nmin = sum;
                result.get(2).clear();
                result.get(3).clear();
                for (int i=0; i<a.length; i++) {
                    if (dig[i] == 0) {result.get(2).add(a[i]);}
                    else {result.get(3).add(a[i]);}
                }
            }            dig[dig.length-1]++;
            for (int i=dig.length-1; i>0; i--) {
                if (dig[i] == 2) {
                    dig[i] = 0;
                    dig[i-1]++;
                } else { break; }
            }
        }        System.out.println("----------任意个元素分组----------");
        for (int i=0; i<2; i++) {System.out.println(result.get(i));}
        System.out.println("----------固定n个元素分组----------");
        for (int i=2; i<4; i++) {System.out.println(result.get(i));}        return result;
    }
}

试试这个“首位法”，和上面的首位法不一样！
新手！代码很粗糙！请包涵！原始数组：2    3    12    21    28    36    43    45    58    78
==开始挑选==================
数组A：2    78    12    45    28
数组B：3    58    21    43    36
==结束挑选=================
|A-B|=|165-161|=4import java.util.Arrays;
public class ArrayAlgorithm
{
public static void main(String args[]){
//int array[] = {1,2,3,4,5,6};       //默认数组array，有2n个元素
int array[] = {2,21,45,43,28,3,78,12,36,58};       //默认数组array，有2n个元素
Arrays.sort(array);              //数组排序
int num = array.length ; //整型变量num等于数组array的长度
int A[] = new int [(num/2)] ;
int B[] = new int [(num/2)]  ; //整型数组A、B
int i = 0,j = 0 ; //数组下标 i 、 j
System.out.print("原始数组：");
printArray(array);               //输出原始数组
System.out.println("");
System.out.println("==开始挑选==================");
if(num%4==0){
for(int x = 0; x<(num/2); x++){   //通过x次挑选，按照算法分出数组A、B
if(x%2==0){
A[i] = array[x] ;
if((++i)<=((A.length)-1))
A[i] = array[(num - 1)-x];
i++;
}else{
B[j]=array[x];
if((++j)<=((B.length)-1))
B[j] = array[(num - 1)-x];
j++;
}
}
}else{
for(int x = 0; x<=(num/2); x++){   //通过x次挑选，按照算法分出数组A、B
if(x%2==0){
A[i] = array[x] ;
if((++i)<=((A.length)-1))
A[i] = array[(num - 1)-x];
i++;
}else{
B[j]=array[x];
if((++j)<=((B.length)-1))
B[j] = array[(num - 1)-x];
j++;
}
}
}
System.out.print("数组A：");
printArray(A);                   //输出数组A
System.out.println("");
System.out.print("数组B：");
printArray(B); //输出数组B
System.out.println("");
System.out.println("==结束挑选=================");
System.out.println("|A-B|=" +"|"+ sumArray(A)+"-"+sumArray(B)+"|="+Math.abs(sumArray(A)-sumArray(B))); }
public static int sumArray(int temp[]){            //数组求和方法
int sum = 0;
for(int x = 0;x< temp.length; x++){
sum+=temp[x];
}
return sum;
}
public static void printArray(int temp[]){         //输出数组方法
for(int x = 0;x<temp.length;x++){
System.out.print(temp[x] + "    ");
}
}
}

目前来看11楼正解
Total sum = 175
26 23 25 sum = 74
24 27 22 sum = 73
Min value = 127楼表现良好,赞~~

调试易

请教一道java面试题

解决方案 »