Article From:https://www.cnblogs.com/airbluecat/p/9684759.html
  1 package com.xxx.utils;
  2 
  3 import com.google.common.primitives.Ints;
  4 
  5 import java.util.*;
  6 
  7 public class ArrayGroupUtils {
  8 
  9     public static void main(String[] args) {
 10 //        int[] arr = {5, 6, 4, 8, 7, 1, 2, 3};//4 5 6 7 8
 11         int[] arr = {1, 2, 5, 6, 6, 9, 10, 17, 18, 2, 8, 20};
 12         List<List<Integer>> lists = minGroup(arr, 30);
 13         for (List<Integer> list : lists) {
 14             System.out.println(list);
 15         }
 16     }
 17 
 18 
 19     /**
 20      * Minimum Grouping Method - Grouping numbers in arrays, requiring the sum of the numbers in each grouping to be less than or equal to k, and finding the minimum number of groupings, each number in the default arr is less than k 21      * <p>
 22      * The first step is to sort the array into an ordered one. 23      * <p>
 24      * The second step: from the first beginning of the array to calculate and exceed K, these are divided into one group. Then we start to calculate the sum of the next group, and finally to the end of the array. 25      * <p>
 26      * The third step: now each group of I has a D[i] to K distance. Now remove all the D[i] of all other groups except the first group. 27      * Starting with the largest number in the first packet, place it in the other packet that holds this number and is the smallest distance from K to D [i]. This process is called division. After splitting, we need to reschedule. 28      * <p>
 29      * Termination condition: if the first group is split completely, then second groups are split like this. Until a group can not be split. 30      *
 31      * @param arr
 32      * @param k
 33      */
 34     public static List<List<Integer>> minGroup(int[] arr, int k) {
 35         //Get ascending list
 36         List<Integer> list = Ints.asList(arr);
 37         Collections.sort(list);
 38 
 39         //Sublist
 40         List<List<Integer>> subList = new ArrayList<>();//-->List<Map<Integer,List> >
 41         List<List<Integer>> resultList = new ArrayList<>();//Return to the result
 42 
 43 
 44         Integer temp = 0;
 45         List<Integer> tempList = new ArrayList<>();
 46 
 47 
 48         for (Integer integer : list) {
 49 
 50             if ((temp + integer) < k) {
 51                 tempList.add(integer);
 52                 temp += integer;
 53             } else if ((temp + integer) > k) {
 54                 temp = integer;
 55                 subList.add(tempList);
 56                 tempList = new ArrayList<>();
 57                 tempList.add(integer);
 58             } else {
 59                 tempList.add(integer);
 60                 temp = 0;
 61                 subList.add(tempList);
 62                 tempList = new ArrayList<>();
 63             }
 64 
 65 
 66         }
 67         subList.add(tempList);//Add the last number.
 68 
 69 
 70         for (int m = 0; m < subList.size(); m++) {
 71             division(subList, resultList, k, m);
 72         }
 73 
 74         //Processing 0 elements in sublist
 75         List<List<Integer>> handZeroEleList = handZeroEle(subList);
 76 
 77         return handZeroEleList;
 78 
 79 
 80     }
 81 
 82 
 83     private static void division(List<List<Integer>> subList, List<List<Integer>> resultList, int k, int m) {
 84 
 85         /*The map for generating D[i]: List is in D[i] ascending order (except for the first grouping).*/
 86         List<Map<Integer, List>> mapList = getSortedList(subList, k, m);
 87 
 88         //Traversing all elements under the first group
 89         List<Integer> subList1 = subList.get(m);
 90         Collections.reverse(subList1);
 91 
 92         for (int n = 0; n < subList1.size(); n++) {
 93             Integer integer = subList1.get(n);
 94             for (int j = 0; j < mapList.size(); j++) {
 95                 Map<Integer, List> listMap = mapList.get(j);
 96                 Integer diTemp = getFirstKey(listMap);
 97                 List<Integer> listTemp = getFirstValue(listMap);
 98                 if (integer > diTemp) {//If you can't put in, compare the next group.
 99                     continue;
100                 } else {//If you can just put it in, repeat the sorting --> continue the loop.101                     //To Riga
102                     listMap.remove(diTemp);
103                     diTemp -= integer;
104                     listTemp.add(integer);
105                     listMap.put(diTemp, listTemp);
106 
107                     //Delete in the first group.108                     //it.remove();
109 //                    integer =  0;
110                     subList1.set(n, 0);
111 
112                     sortByCustom(mapList);
113                     break;
114 
115                 }
116             }
117         }
118         resultList.add(subList1);
119 
120     }
121 
122 
123     /**
124      * Get rid of the first packet and sort all other packets by D[i].125      *
126      * @param subList
127      * @param k
128      * @return
129      */
130     private static List<Map<Integer, List>> getSortedList(List<List<Integer>> subList, int k, int m) {
131         List<Map<Integer, List>> mapList = new ArrayList<>();
132         for (int i = m + 1; i < subList.size(); i++) {
133             Map<Integer, List> tempMap = new HashMap<>();
134             tempMap.put(k - listSum(subList.get(i)), subList.get(i));
135             mapList.add(tempMap);
136         }
137         sortByCustom(mapList);
138         return mapList;
139     }
140 
141 
142     /**
143      * sort144      *
145      * @param mapList
146      * @return
147      */
148     private static void sortByCustom(List<Map<Integer, List>> mapList) {
149         Collections.sort(mapList, new Comparator<Map<Integer, List>>() {
150             @Override
151             public int compare(Map<Integer, List> o1, Map<Integer, List> o2) {
152                 if (getFirstKey(o1) > getFirstKey(o2)) {
153                     return 1;
154                 }
155                 if (getFirstKey(o1) == getFirstKey(o2)) {
156                     return 0;
157                 }
158                 return -1;
159             }
160         });
161     }
162 
163 
164     /**
165      * Seek array and166      *
167      * @param arr
168      * @return
169      */
170     public static int arraySum(int[] arr) {
171         int sum = 0;
172         for (int i : arr) {
173             sum += i;
174         }
175         return sum;
176     }
177 
178     /**
179      * Seek list< integer> sum.180      *
181      * @param list
182      * @return
183      */
184     public static Integer listSum(List<Integer> list) {
185         Integer sum = 0;
186         for (Integer integer : list) {
187             sum += integer;
188         }
189         return sum;
190     }
191 
192 
193     /**
194      * Get the first key value in map195      *
196      * @param map data source197      * @return
198      */
199     private static Integer getFirstKey(Map<Integer, List> map) {
200         Integer obj = null;
201         for (Map.Entry<Integer, List> entry : map.entrySet()) {
202             obj = entry.getKey();
203             if (obj != null) {
204                 break;
205             }
206         }
207         return obj;
208     }
209 
210 
211     /**
212      * Get the first data value in map213      *
214      * @param map data source215      * @return
216      */
217     private static List getFirstValue(Map<Integer, List> map) {
218         List obj = null;
219         for (Map.Entry<Integer, List> entry : map.entrySet()) {
220             obj = entry.getValue();
221             if (obj != null) {
222                 break;
223             }
224         }
225         return obj;
226     }
227 
228 
229     /**
230      * [0, 6, 6, 5, 0, 0]231      * [0, 0, 17, 10]
232      * [2, 1, 9, 18]0 of it goes away.233      *
234      * @param subList
235      */
236     private static List<List<Integer>> handZeroEle(List<List<Integer>> subList) {
237         List<List<Integer>> resultList = new ArrayList<>();
238         for (List<Integer> integers : subList) {
239             List<Integer> list = new ArrayList<>();
240             for (Integer integer : integers) {
241                 if (integer != 0) {
242                     list.add(integer);
243                 }
244             }
245             if (list.size() > 0) {
246                 resultList.add(list);
247             }
248 
249         }
250         return resultList;
251     }
252 
253 }

 

Leave a Reply

Your email address will not be published. Required fields are marked *