Пожалуйста, проверьте эту логику, которую я написал для этой проблемы. Это сработало для нескольких сценариев, которые я проверил. Пожалуйста, прокомментируйте решение,
Подход:
- Сортируйте основной массив и разделите его на 2 команды.
- Затем начните делать команду равной по сдвигу и переставлять элементы из одного массива в другой, основываясь на условиях, упомянутых в коде.
Если разница состоит в том, что разница в сумме меньше минимального числа большего массива (массива с большей суммой), то смещение элементов из большего массива в меньший массив. Смещение происходит с условием , этот элемент из массива большего размера со значением, меньшим или равным разнице. Когда все элементы из массива большего размера больше разницы, смещение останавливается и происходит обмен. Я просто поменяю местами последние элементы массива (это можно сделать эффективнее, найдя, какие два элемента поменять местами), но все же это сработало. Дайте мне знать, если эта логика не удалась в любом сценарии
public class SmallestDifference {
static int sum1 = 0, sum2 = 0, diff, minDiff;
private static List<Integer> minArr1;
private static List<Integer> minArr2;
private static List<Integer> biggerArr;
/**
* @param args
*/
public static void main(String[] args) {
SmallestDifference sm = new SmallestDifference();
Integer[] array1 = { 2, 7, 1, 4, 5, 9, 10, 11 };
List<Integer> array = new ArrayList<Integer>();
for (Integer val : array1) {
array.add(val);
}
Collections.sort(array);
CopyOnWriteArrayList<Integer> arr1 = new CopyOnWriteArrayList<>(array.subList(0, array.size() / 2));
CopyOnWriteArrayList<Integer> arr2 = new CopyOnWriteArrayList<>(array.subList(array.size() / 2, array.size()));
diff = Math.abs(sm.getSum(arr1) - sm.getSum(arr2));
minDiff = array.get(0);
sm.updateSum(arr1, arr2);
System.out.println(arr1 + " : " + arr2);
System.out.println(sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff);
int k = arr2.size();
biggerArr = arr2;
while (diff != 0 && k >= 0) {
while (diff != 0 && sm.findMin(biggerArr) < diff) {
sm.swich(arr1, arr2);
int sum1 = sm.getSum(arr1), sum2 = sm.getSum(arr2);
diff = Math.abs(sum1 - sum2);
if (sum1 > sum2) {
biggerArr = arr1;
} else {
biggerArr = arr2;
}
if (minDiff > diff || sm.findMin(biggerArr) > diff) {
minDiff = diff;
minArr1 = new CopyOnWriteArrayList<>(arr1);
minArr2 = new CopyOnWriteArrayList<>(arr2);
}
sm.updateSum(arr1, arr2);
System.out.println("Shifting : " + sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff);
}
while (k >= 0 && minDiff > array.get(0) && minDiff != 0) {
sm.swap(arr1, arr2);
diff = Math.abs(sm.getSum(arr1) - sm.getSum(arr2));
if (minDiff > diff) {
minDiff = diff;
minArr1 = new CopyOnWriteArrayList<>(arr1);
minArr2 = new CopyOnWriteArrayList<>(arr2);
}
sm.updateSum(arr1, arr2);
System.out.println("Swapping : " + sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff);
k--;
}
k--;
}
System.out.println(minArr1 + " : " + minArr2 + " = " + minDiff);
}
private void updateSum(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) {
SmallestDifference sm1 = new SmallestDifference();
sum1 = sm1.getSum(arr1);
sum2 = sm1.getSum(arr2);
}
private int findMin(List<Integer> biggerArr2) {
Integer min = biggerArr2.get(0);
for (Integer integer : biggerArr2) {
if(min > integer) {
min = integer;
}
}
return min;
}
private int getSum(CopyOnWriteArrayList<Integer> arr) {
int sum = 0;
for (Integer val : arr) {
sum += val;
}
return sum;
}
private void swap(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) {
int l1 = arr1.size(), l2 = arr2.size(), temp2 = arr2.get(l2 - 1), temp1 = arr1.get(l1 - 1);
arr1.remove(l1 - 1);
arr1.add(temp2);
arr2.remove(l2 - 1);
arr2.add(temp1);
System.out.println(arr1 + " : " + arr2);
}
private void swich(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) {
Integer e;
if (sum1 > sum2) {
e = this.findElementJustLessThanMinDiff(arr1);
arr1.remove(e);
arr2.add(e);
} else {
e = this.findElementJustLessThanMinDiff(arr2);
arr2.remove(e);
arr1.add(e);
}
System.out.println(arr1 + " : " + arr2);
}
private Integer findElementJustLessThanMinDiff(CopyOnWriteArrayList<Integer> arr1) {
Integer e = arr1.get(0);
int tempDiff = diff - e;
for (Integer integer : arr1) {
if (diff > integer && (diff - integer) < tempDiff) {
e = integer;
tempDiff = diff - e;
}
}
return e;
}
}